[BAEKJOON] 14168. 총깡총깡
Posted on
문제 :
동물 애호가 진서는 총깡총깡 뛰는 동물과 짝폴짝폴 뛰는 동물들을 K마리씩 키운다. 타지로 취업하게 된 진서는 내일 이사를 한다.
이사하게 될 집에서 같이 살게 될 룸메이트 일호는 동물을 싫어하기 때문에 진서는 근처의 집에 동물들을 한마리씩 맡길 예정이다.
진서가 동물들을 맡길 수 있는 집의 종류는 A형 집과 B형 집 2종류 이다.
우연하게도 짝폴짝폴 뛰는 동물과 총깡총깡 뛰는 동물, A형 집, B형 집의 수는 모두 같다.
진서는 총깡총깡 뛰는 동물들과 짝폴짝폴 뛰는 동물들을 같은 종류의 집에 통일 시켜 맡기고 싶다.
하지만 진서는 총깡총깡 뛰는 동물들을 약간 더 좋아하므로 각 집에서 동시에 출발하여 진서네 집으로 가장 빨리 도착하는 동물이 총깡총깡 뛰는 동물이길 원한다.
진서가 살게 될 집, A형 집, B형 집, A형 집도 B형 집도 아닌 집이 있는 지도가 주어질 때 총깡총깡 뛰는 동물이 A형 집에 살아야 할 지 B형집에 살아야 할지 출력하고 가장 빨리 도착하는 총깡총깡 뛰는 동물이 진서네 집으로 부터 얼마만큼 떨어져 있는지 출력하라.
(만약 총깡총깡 뛰는 동물들이 A형집에 살던 B형집에 살던 상관이 없는 경우는 A형집에 살기로 한다.)
입력 :
입력의 첫 번째 줄에 전체 집의 수 N과 집과 집사이를 연결하는 도로 M이 공백으로 주어진다. (3 ≤ N ≤ 5,000, 3 ≤ M ≤ 20,000)
입력의 둘째 줄에 진서의 집 J가 주어진다 (1 ≤ J ≤ N)
입력의 셋째 줄에 종류별 동물의 수 K가 주어진다. (2*K ≤ N)
입력의 넷째 줄에 K개의 A형 집이 공백으로 구분되어 주어진다.
입력의 다섯 번째 줄에 K개의 B형 집이 공백으로 구분되어 주어진다.
이후 M개의 줄에 X Y Z(1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)가 주어진다. 이는 X번 집과 Y번 집 사이에 Z의 길이를 가지는 도로가 존재한다는 것이다.
출력 :
총깡총깡 뛰는 동물이 살게 될 집의 종류를 말한 뒤 다음줄에 거리를 출력한다.
A형 집에서만 진서의 집에 갈 수 있는 경우 A를 출력한 뒤 다음 줄에 거리를 출력, B형 집에서만 진서의 집에 갈 수 있는 경우 B를 출력한 뒤 다음 줄에 거리를 출력, A형 집, B형 집 둘다 진서의 집에 갈 수 없는 경우에는 –1을 출력한다.
풀이 :
골드 1 문제인 것에 비해 다익스트라를 활용하면 비교적 쉽게 풀 수 있는 문제였다.
우선 집의 종류에는 A형, B형, A형도 B형도 아닌 것 이렇게 3가지의 종류가 있다.
이 때 다익스트라 알고리즘을 활용하여 각 집 사이의 최단 거리를 구하는 동시에 3가지의 종류 별 최단 거리도 동시에 구해준다.
이렇게 된다면 다익스트라를 한 번 계산하고 3가지 종류의 각 최단거리를 구할 수 있다.
A형과 B형 거리가 없다면 두 종류의 집에 모두 연결되어있지 않은 것이기 때문에 -1을 출력한다.
A형 거리가 B형 거리보다 작거나 같다면 A형 거리를 출력한다.
이 외에는 B형 거리를 출력한다.
코드 :
코드 보기/접기
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#define MAX 987654321
#define pii pair<int, int>
using namespace std;
int homenum[5001], dist[5001], n, ansdist[3];
vector<vector<pii>> adj;
void inputCharacter(int n, int k) {
int num;
for (int i = 0; i < k; i++) {
cin >> num;
homenum[num] = n;
}
}
void dijkstra(int home) {
fill_n(dist, n + 1, MAX);
fill_n(ansdist, 3, MAX);
priority_queue<pii, vector<pii >, greater<>> pq;
pq.push(pii(0, home));
while (!pq.empty()) {
int curdist = pq.top().first, curidx = pq.top().second, curnum = homenum[curidx];
pq.pop();
if (dist[curidx] == -1) continue;
dist[curidx] = -1;
ansdist[curnum] = min(ansdist[curnum], curdist);
int size = adj[curidx].size();
for (int k = 0; k < size; k++) {
int cmpidx = adj[curidx][k].first, cmpdist = adj[curidx][k].second + curdist;
if (dist[cmpidx] > cmpdist) {
dist[cmpidx] = cmpdist;
pq.push(pii(cmpdist, cmpidx));
}
}
}
}
int main() {
int m, home, k, i, fir, sec, d;
cin >> n >> m >> home >> k;
adj.resize(n + 1);
inputCharacter(1, k);
inputCharacter(2, k);
for (i = 0; i < m; i++) {
cin >> fir >> sec >> d;
adj[fir].push_back(pii(sec, d));
adj[sec].push_back(pii(fir, d));
}
dijkstra(home);
if (ansdist[1] == MAX && ansdist[2] == MAX) cout << -1 << '\n';
else if (ansdist[1] <= ansdist[2]) cout << "A\n" << ansdist[1] << '\n';
else cout << "B\n" << ansdist[2] << '\n';
return 0;
}