[백준] 11779번 - 최소비용 구하기 2 (Gold 3)

문제 링크

백준 11779번 - 최소비용 구하기 2 (Gold 3)

문제 설명

n($\leq$ 1000)개의 도시와 도시 사이를 단방향으로 연결하는 m($\leq$ 100,000)개의 버스가 있다.
각 버스를 이용하는데 드는 비용은 0 이상 100,000 이하의 정수이다.
A번째 도시에서 B번째 도시로 버스를 통해 이동하고자 할 때 드는 최소 비용과 경로를 출력하시오.
단, 이동이 불가능한 경우는 주어지지 않는다고 가정한다.

정답 코드 및 설명

최소 비용을 구하는 것은 다익스트라 알고리즘을 사용하면 되므로 쉽다.
문제는 경로를 구하는 과정이다.
보통의 다익스트라에서는 각 지점에 도착하기 위한 최소 비용만을 저장하는데, 각 지점에 도착하기 위한 최단 경로에서의 직전 위치를 함께 저장하면 경로를 역추적할 수 있다.
코드의 31행 ~ 51행이 경로의 역추적을 고려한 다익스트라 알고리즘을 수행하는 과정에 해당한다.

일단 직전 위치를 함께 저장했다면, 경로의 역추적은 직전 위치를 계속 따라가는 식으로 수행하면 된다.
자세한 역추적 과정은 코드의 54행 ~ 69행을 참조하면 된다.

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

public class BOJ11779 {
    final int INF = 1_000_000_000;
    int n;
    Integer[][] bus;
    int start, end;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        bus = new Integer[n][n];
        StringTokenizer st;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());
            if (bus[start][end] == null || cost < bus[start][end])
                bus[start][end] = cost;
        }
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken()) - 1;
        end = Integer.parseInt(st.nextToken()) - 1;
    }

    int[][] Dijkstra(int start) {
        int[][] minCost = new int[n][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        for (int i = 0; i < n; i++)
            minCost[i][0] = INF;
        minCost[start][0] = 0;
        minCost[start][1] = start;
        pq.add(new int[]{start, 0, start});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            if (minCost[curr[0]][0] < curr[1]) continue;
            for (int i = 0; i < n; i++) {
                if (bus[curr[0]][i] == null) continue;
                if (bus[curr[0]][i] + minCost[curr[0]][0] < minCost[i][0]) {
                    minCost[i][0] = bus[curr[0]][i] + minCost[curr[0]][0];
                    minCost[i][1] = curr[0];
                    pq.add(new int[]{i, minCost[i][0], minCost[i][1]});
                }
            }
        }
        return minCost;
    }

    void traceback(int start, int end) {
        int[][] minCost = Dijkstra(start);
        System.out.println(minCost[end][0]);
        Stack<Integer> cities = new Stack<>();
        int curr = end;
        cities.push(curr);
        while (curr != start) {
            curr = minCost[curr][1];
            cities.push(curr);
        }
        System.out.println(cities.size());
        StringBuilder sb = new StringBuilder();
        while (!cities.isEmpty()) {
            sb.append(cities.pop() + 1).append(' ');
        }
        System.out.println(sb);
    }

    void solution() throws IOException {
        input();
        traceback(start, end);
    }

    public static void main(String[] args) throws IOException {
        new BOJ11779().solution();
    }
}