[백준 | Java] 11779 최소비용 구하기2

내 풀이

다익스트라로 최소경로 탐색에 경로를 추적하는 기능을 추가한 문제다.

최소경로의 경로 추적을 위해서는 prev 배열을 사용해 각 노드에 도달하기 전의 노드를 저장한다.
prev[i]는 노드 i로 오는 최단 경로에서 이전 노드를 저장하며, i노드에 도달하기 직전에 어떤 노드를 거쳤는지 기록한다.

예를 들어, n노드(도착점)에서 시작해 s노드(출발점)까지 prev배열을 따라가면, n(도착점) → prev[n] → prev[prev[n]] → s(출발점) 순으로 경로를 추적할 수 있다.
따라서 도착점에서 시작해 출발점으로 거꾸로 추적해야 전체 경로를 알 수 있다.

예시
만약 경로가 1 → 3 → 5 → 7이라면, prev 배열은 다음과 같이 채워진다.

• prev[7] = 5
• prev[5] = 3
• prev[3] = 1
  
  이후 경로를 추적하면 7 → 5 → 3 → 1로 역순으로 나열된다.
  이 경로를 올바르게 출력하기 위해 Collections.reverse()를 통해 1 → 3 → 5 → 7로 바꾸어 출력한다.

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m, s, e;
    static List<int[]>[] map;
    static int[] prev;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        map = new ArrayList[n + 1];
        prev = new int[n + 1];
        Arrays.fill(prev, -1);

        for (int i = 0; i < n; i++) {
            map[i + 1] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[a].add(new int[]{b, c});
        }
        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        long minCost = di();
        List<Integer> path = getPath();

        System.out.println(minCost);
        System.out.println(path.size());
        for (int city : path) {
            System.out.print(city + " ");
        }
    }

    static long di() {
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o[1]));
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[s] = 0;
        pq.add(new long[]{s, 0});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            int curNode = (int)cur[0];

            if (cur[1] > dist[curNode]) continue;

            for (int[] neighbor : map[curNode]) {
                int nextNode = neighbor[0];
                long nDist = dist[curNode] + neighbor[1];

                if (nDist < dist[nextNode]) {
                    dist[nextNode] = nDist;
                    pq.add(new long[]{nextNode, nDist});
                    prev[nextNode] = curNode;  // 각 노드에 도달하기 전의 노드 저장
                }
            }
        }
        return dist[e];
    }

    static List<Integer> getPath() {
        List<Integer> path = new ArrayList<>();
        for (int i = e; i != -1; i = prev[i]) {
            path.add(i);
        }
        Collections.reverse(path);
        return path;
    }
}