18223번
문제
종강을 맞은 민준이는 고향인 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이다.
그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다.
지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다. 정점은 1~V까지 있다. 건우는 P번 정점에 있다. 그리고 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다. 중복되는 간선과 자기 자신을 가리키는 간선은 존재하지 않는다.
아래와 같은 그래프가 있을 때,
위의 경우는 최단 경로가 두 가지 있다. 1→3→4→5→6 또는 1→3→5→6 이다. 이것 중에서 건우가 있는 곳, 즉 4번 정점이 포함된 최단 경로가 있으므로 이 경우에는 민준이가 건우를 도울 수 있다.
민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.
어쩌면 지킬 수도 있는 민준이의 우정을 위해 우리가 도와주자!
문제 해결 순서
- 간선에 비중치가 있는 다익스트라 유형의 문제.
- 다익스트라를 구현후 1부터 v까지의 최소거리와 1부터 P까지의 최소거리 + P부터 V까지의 최소거리를 비교
- 만약 같다면 건우를 도울 수 있고, 다르다면 건우를 도울 수 없다.
import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
int end, weight;
public Node(int end, int weight){
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
public class Main {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static final int INF = 100_000_000;
static int v,e,k;
// 모든 정점을 저장할 배열을 List로 만드는데, List에는 배열 i번째와 연결된 모든 노드들이 저장된다.
static List<Node>[] list;
// 시작 노드를 기준으로 다른 모든 노드까지의 최소 비용 배열
static int[] dist;
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
list = new ArrayList[v + 1];
dist = new int[v + 1];
Arrays.fill(dist, INF);
for(int i = 1; i <= v; i++){
list[i] = new ArrayList<>();
}
// 리스트에 그래프 정보를 초기화
for(int i = 0 ; i < e; i++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
// start에서 end로 가는 weight 가중치
list[start].add(new Node(end, weight));
list[end].add(new Node(start, weight));
}
StringBuilder sb = new StringBuilder();
// 다익스트라 알고리즘
// 문제핵심 구현 부분
dijkstra(1);
int masan = dist[v];
int geonoo = dist[k];
dijkstra(k);
geonoo += dist[v];
if (masan == geonoo){
bw.write("SAVE HIM");
}
else
bw.write("GOOD BYE");
bw.flush();
br.close();
}
private static void dijkstra(int start){
// 우선순위 큐 선언
PriorityQueue<Node> queue = new PriorityQueue<>();
// 노드 방문 체크 변수 선언
boolean[] check = new boolean[v + 1];
// 우선순위 큐에 탐색을 시작할 노드를 삽입
queue.add(new Node(start, 0));
// 최소비용 배열 시작번째 초기화
dist[start] = 0;
// 큐가 비어있지 않다면
while(!queue.isEmpty()){
// 큐에서 뺀 노드를 현재 노드에 저장
Node curNode = queue.poll();
// 현재 노드의 번째를 저장
int cur = curNode.end;
// 현재 노드를 방문했으면 패스, 방문하지 않았으면 최소비용 검사
if(check[cur] == true) continue;
check[cur] = true;
// 현재 노드와 연결된 모든 노드를 돌아가며 수행
for(Node node : list[cur]){
// 만약 최소비용 배열에 저장된 값(시작 노드에서부터 연결된 노드까지)이 현재 노드에서부터 연결된 노드까지의 값보다 크다면
// 맨 위의 그림을 예로들면 노드 1(시작노드)에서부터 노드 3(연결된 노드)까지의 값이 노드 4(현재 노드)에서부터 노드 3(연결된 노드)의 값보다 크다면
// 6 > 3 + 1
if(dist[node.end] > dist[cur] + node.weight){
// 최소비용 배열의 [연결된 노드] 번째의 값을 교체
dist[node.end] = dist[cur] + node.weight;
// 큐에는 연결된 노드를 추가
queue.add(new Node(node.end, dist[node.end]));
}
}
}
}
}