아이디어

• 최단경로 찾는 문제니 Dijkstra로 푼다.
  • $O(V^2)$이어도 상관 없다.
• 경로 찾는 방법
  1. 어떤 점에 도달하는 최단경로는, 그 점의 이전 점까지 도달하기 위한 최단경로를 반드시 지난다.
  2. Dijkstra는 시점부터 종점까지 거치는 모든 경로상 점에 대해 최단거리를 구할 수 있다.
  3. Dijkstra는 마지막으로 변경된 거릿값이 최단거리가 된다.
  • 그러므로, 각 정점에 대해 최단거리가 갱신될 때마다 그 정점으로 들어오는 점의 번호를 기록한다.
    • 이는 자식에서 부모로 향하는 트리 구조를 가질 것이다.
  • 종점에서부터 번호를 역추적하며 역순으로 경로의 정점을 기록한 뒤 출력하면 경로를 출력할 수 있다.
  • 문제에는 서로 같은 도시에서 출발해 같은 도시로 도착하는 버스가 없다는 보장이 없다! 따라서 그래프에는 그러한 버스의 비용 중 작은 것만 기록해야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int n, m, A, B, cnt;
	static int[][] graph;
	static int[] dist, path;
	static boolean[] visited;
	
	static final int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(rd.readLine());
		m = Integer.parseInt(rd.readLine());
		
		graph = new int[n+1][n+1];
		for (int i=0; i<=n; i++) {
			for (int j=0; j<=n; j++) {
				graph[i][j] = i == j ? 0 : INF;
			}
		}
		
		for (int i=0; i<m; i++) {
			tk = new StringTokenizer(rd.readLine());
			int s = Integer.parseInt(tk.nextToken());
			int e = Integer.parseInt(tk.nextToken());
			int w = Integer.parseInt(tk.nextToken());
			graph[s][e] = Math.min(graph[s][e], w);
		}
		
		tk = new StringTokenizer(rd.readLine());
		A = Integer.parseInt(tk.nextToken());
		B = Integer.parseInt(tk.nextToken());
		
		
		dist = new int[n+1];
		Arrays.fill(dist, INF);
		dist[A] = 0;
		visited = new boolean[n+1];

		path = new int[n+1];
		
		int mi = 0;
		do {
			// find min unvisited dist idx
			mi = 0;
			for (int i=1; i<=n; i++) {
				if (!visited[i] && dist[i] < dist[mi]) {
					mi = i;
				}
			}
			
			visited[mi] = true;
			
			// dist update
			for (int i=1; i<=n; i++) {
				if (dist[mi] + graph[mi][i] < dist[i]) {
					dist[i] = dist[mi] + graph[mi][i];
					path[i] = mi;
				}
			}
		} while (mi != B);
		
		// path backtracking
		int i = B;
		while (i != 0) {
			cnt++;
			sb.insert(0, ' ').insert(0, i);
			i = path[i];
		}
		
		System.out.println(dist[B]);
		System.out.println(cnt);
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 45884 KB
• 시간: 448 ms

리뷰

• 1번 버전(1916번)에서도 마지막 아이디어 때문에 당했는데, 또 당했다!
• 경로를 추적하는 방법을 떠올리는 게 재밌었다.