백준 | 18223번. 민준이와 마산 그리고 건우 - 다익스트라

⬛ 백준 18223번. 민준이와 마산 그리고 건우 - 다익스트라 

https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

문제

종강을 맞은 민준이는 고향인 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이다.

그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다.

지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다. 정점은 1~V까지 있다. 건우는 P번 정점에 있다.

그리고 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다.

중복되는 간선과 자기 자신을 가리키는 간선은 존재하지 않는다.

아래와 같은 그래프가 있을 때,

위의 경우는 최단 경로가 두 가지 있다.

1→3→4→5→6 또는 1→3→5→6 이다. 이것 중에서 건우가 있는 곳, 즉 4번 정점이 포함된 최단 경로가 있으므로 이 경우에는 민준이가 건우를 도울 수 있다.

민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.

어쩌면 지킬 수도 있는 민준이의 우정을 위해 우리가 도와주자!

입력

입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E*,* 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V  ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P  ≤ V)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가 공백으로 구분되어 주어진다. 이는 a번 정점과 b번 정점 사이의 거리가 c임을 의미한다. (1 ≤ a,b ≤ V, 1 ≤ c  ≤ 10,000)

출력

민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력한다.

💚 1차 시도

• 처음에는 1→ V로 가는 최단 경로를 구해놓고, 경로 역추적으로 parent배열에 직전 방문 정점 담아두어, 해당 경로에 P가 존재한다면 건우를 거쳤다고 생각하고 문제를 풀어서 틀렸다.
• 민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.
• 이 문제의 핵심은 저 문장에 있다.
• 1→ P → V 거쳐 가는 거리와 1→V 직진 거리를 비교했을 떄 거리가 똑같다면 P를 거쳐가겠다는 의미였는데 내가 너무 성급하게 푸느라 놓쳤다. 주의하자.

import java.util.*;
import java.util.Scanner;

/*18223번. 민준이와 마산 그리고 건우 - 다익스트라 문풀 
 잘못 풀었따. ㅠㅠ 경로 역추적을 쓸 필요 없는 문제다. */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}

public class Main {
	static int V, E, P;
	static int[] parent;//직전 정점 담는 용도 
	static int[] distance;// 거리 저장용 
	static boolean[] visited;//체크용 
	static ArrayList<ArrayList<Edge>> graph;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		V = kb.nextInt();
		E = kb.nextInt();
		P = kb.nextInt();
		
		parent= new int[V+1];//1번 부터니까 
		distance = new int[V+1];
		visited = new boolean[V+1];//초기화 안했었구나
		
		graph = new ArrayList<>();
		for(int i=0; i<=V; i++) {
			graph.add(new ArrayList<>());
		}
		
		Arrays.fill(distance, Integer.MAX_VALUE);//초기화 시켜놓고 
		
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			int val = kb.nextInt();
			//양방향 
			graph.get(a).add(new Edge(b, val));
			graph.get(b).add(new Edge(a, val));
		}
		
		//다익스트라 시작 
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		distance[1]= 0;//시작점은 고정1 
		pQ.offer(new Edge(1, 0));
		parent[1] = 0;
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			
			for(Edge nx : graph.get(cur.e)) {
				if(!visited[nx.e] && distance[nx.e] > distance[cur.e] + nx.val) {
					//부모도 저장해주기 
					parent[nx.e] = cur.e;//직전 정점 담기 
					distance[nx.e] = distance[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}
		
		//parent에 직전 정점은 담겨져 있고,
		Stack<Integer> stack = new Stack<>();
		//경로 역추적 로직 중요하다. 
		int cur = V;//1) 도착지점을 cur로 설정 
		stack.push(cur);//2) 우선 담아둔다 
		
		while(parent[cur] != 0) { //cur의 부모가 0이 아닌동안 반복하면서
			cur = parent[cur];//부모로 거슬러올라가고/
			stack.push(cur);//스택에 담는다.//->부모가 0되면 탈출 
		}
		
		boolean flag = false; //안존재 
		//경로 안에 P가 존재하면 
		while(!stack.isEmpty()) { //빈 상태 될 때까지 반복해야 경로가 나옴
			System.out.print(stack.pop()+ " ");
		}
	}
}

 

💚 2차 시도 | 그냥 길이만 비교하면 된다.

• 드디어 풀림 ㅠㅠ

1→ V 로 가는 최단 거리와 1→P → V 거쳐 가는 최단 거리 비교해서 둘이 같다면 save 아니면 good bye 출력하면 된다.

package to_0831_9;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//다시 풀기
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int V, E, P;
	static ArrayList<ArrayList<Edge>> graph;
	//다익스트라 
	static int dijkstra(int s, int e) {
		int[] dist = new int[V+1];
		Arrays.fill(dist, Integer.MAX_VALUE); //최댓값 세팅 
		boolean[] visited = new boolean[V+1];
		PriorityQueue<Edge> pQ =new PriorityQueue<>();
		
		//시작점 처리
		dist[s] = 0;
		pQ.offer(new Edge(s, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e ] =true;
			
			for(Edge nx : graph.get(cur.e)) {
				if(!visited[nx.e] && dist[nx.e] > dist[cur.e] + nx.val) {
					dist[nx.e] = dist[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, dist[nx.e]));
				}
			}
		}
		return dist[e];//목적지까지의 최단거리 리턴
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		V = kb.nextInt();
		E = kb.nextInt();
		P = kb.nextInt();
		
		graph = new ArrayList<>();
		for(int i=0; i<=V; i++) graph.add(new ArrayList<>());
		
		//데이터 입력 받기 
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			//양방향 
			graph.get(a).add(new Edge(b, c));
			graph.get(b).add(new Edge(a, c));
		}
		//1) 1-> V 직진 하기 
		int len1 = dijkstra(1, V);
		
		//2) 1-> P -> V 거쳐가기 
		int len2 = dijkstra(1, P) + dijkstra(P, V);
		//최종 답 출력 
		if(len1 == len2) {
			System.out.println("SAVE HIM");
		}else {
			System.out.println("GOOD BYE");
		}
	}
}