[BOJ_9694] 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 Java (다익스트라, 경로 추적)

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_9694 {

    static final int MAX = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int test=1; test<=t; test++) {
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(stk.nextToken());
            int m = Integer.parseInt(stk.nextToken());
            int[][] map = new int[m][m];
            int[] parent = new int[m]; // 경로 추적을 위함
            Arrays.fill(parent, -1);

            for(int[] row : map)
                Arrays.fill(row, MAX);

            // 관계 input
            for(int i=0; i<n; i++) {
                stk = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(stk.nextToken());
                int y = Integer.parseInt(stk.nextToken());
                int z = Integer.parseInt(stk.nextToken());

                map[x][y] = z;
                map[y][x] = z;
            }

            System.out.print("Case #" + test + ": ");
            Stack<Integer> result = dijkstra(m, map, parent);
            while(!result.isEmpty()) {
                System.out.print(result.pop() + " ");
            }
            System.out.println();
        }
    }

    public static Stack<Integer> dijkstra(int m, int[][] map, int[] parent) {
        Queue<Integer> q = new PriorityQueue<>();
        int[] dist = new int[m];
        Arrays.fill(dist, MAX);

        Stack<Integer> history = new Stack<>();

        q.offer(0);
        dist[0] = 0;

        while(!q.isEmpty()) {
            int here = q.poll();

            // 모든 정점 탐색 ㄱㄱ
            for(int i=0; i<m; i++) {
                // 연결되어 있고 && here를 거치는 것이 지금 알고있는 최단거리보다 짧으면 갱신
                if(map[here][i] != MAX && dist[i] > dist[here]+map[here][i]) {
                    dist[i] = dist[here]+map[here][i];
                    q.offer(i);

                    parent[i] = here;
                }
            }
        }

        if(parent[m-1] == -1) {
            history.push(-1);
        }
        else {
            int index = m-1;
            while(index != -1) {
                history.push(index);
                index = parent[index];
            }
        }

        return history;
    }
}

• 가중치가 다른 노드의 최단거리를 구하기 위해 다익스트라 알고리즘을 사용해야 합니다.
• 이 문제에서는 추가로 다익스트라의 경로를 추적해야 합니다..

🍄 다익스트라에서의 경로 추적

경로 추적을 위해 int[] parent 배열을 선언하였습니다.
parent[index]의 의미는, 시작점에서 index번 노드까지 최단거리로 이동할 때 거쳐야하는 노드입니다.
그래서 최단거리가 갱신될 때 parent도 갱신해줍니다.

다익스트라 탐색이 끝나면,
parent 배열을 끝에서부터 탐색합니다.

예를 들어볼까요?

저는 0에서 시작하여 4로 가는 최단거리의 경로를 알고 싶습니다.
다익스트라 알고리즘에서 최단거리가 갱신될 때마다 parent를 갱신하게 되면
다익스트라 탐색이 끝난 후 parent 배열은
-1, 0, 0, 1, 2 가 됩니다.

끝(도착점)에서 부터 탐색해보면..
parent[4] == 2
parent[2] == 0
parent[0] == -1 << 끝

parent 배열의 인덱스를 보면 바로 우리가 찾던 경로라는 것을 알 수 있습니다. 😀