[백준 P11779] 최소비용 구하기 2 자바 Java

P11779 최소비용 구하기 2

11779번: 최소비용 구하기 2

 

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

 

입력값

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

 

출력값

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

4
3
1 3 5

 

알고리즘

1916번 문제의 확장된 버전으로 생각하면 된다.

[백준 P1916] 최소비용구하기 자바 Java

 

1916번 문제의 코드를 그대로 사용하면서 경로를 트래킹할 하나의 메서드를 추가로 구현한다. 지나온 경로를 저장하는 방법은 생각보다 간단한다. 기존 다익스트라 코드에서 출발지에서 특정 정점까지 최소비용을 저장해두는 path 배열을 업데이트 하는 부분을 살펴보자.

while (!pq.isEmpty()) {
    int[] current = pq.poll();

    if (path[current[0]] < current[1]) continue;

    for (int[] next: graph[current[0]]) {
        int weight = path[current[0]] + next[1];

        if (path[next[0]] > weight) {
            pq.add(new int[] {next[0], weight});
            path[next[0]] = weight;
            dest[next[0]] = current[0];
        }
    }
}

path 배열이 업데이트 되는 경우는 이미 저장된 비용보다 더 작은 비용으로 그 정점까지 갈 수 있는 경로를 발견한 경우이다. 그렇게 path 배열을 업데이트 할 경로를 발견할 때, 그 간선의 출발지를 따로 기록해둔다. 이를 기록할 배열은 dest 배열로 선언했다.

결론적으로, 모든 탐색을 마친 뒤 최소비용을 구하면, 출발지에서부터 각 정점까지의 최소비용이 path 배열에 담기게 된다. 추가로, 각 정점까지 최소비용으로 가기 위해서 바로 직전에 도착해야 하는 정점의 번호가 dest에 담긴다.

 

이제 출발지에서부터 도착지까지 경로를 구해야한다. 도착지부터 시작하여 dest 배열을 인덱싱하면서 도착지에 최소비용으로 도달하기 위해 바로 직전에 어느 정점을 거쳐야 하는지를 구한다. 그 정점들을 모두 route라는 리스트에 넣어주면 출발지에서 목적지까지 최소비용으로 갈 수 있는 최단 경로를 구할 수 있다.

 

전체 코드는 아래와 같다.

 

코드

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

public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int N, M;
    static int start, end;
    static int[] dest;
    static int[] path;
    static List<int[]>[] graph;
    static List<Integer> route;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        path = new int[N + 1];
        dest = new int[N + 1];

        Arrays.fill(path, INF);

        route = new ArrayList<>();
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph[from].add(new int[] {to, weight});
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        findPath();
        findRoute();

        System.out.println(path[end]);
        System.out.println(route.size());

        for (int i = route.size() - 1; i >= 0; i--) {
            System.out.print(route.get(i) + " ");
        }
        System.out.println();
    }

    public static void findPath() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[1] - b[1];
        });
        path[start] = 0;
        pq.add(new int[] {start, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();

            if (path[current[0]] < current[1]) continue;

            for (int[] next: graph[current[0]]) {
                int weight = path[current[0]] + next[1];

                if (path[next[0]] > weight) {
                    pq.add(new int[] {next[0], weight});
                    path[next[0]] = weight;
                    dest[next[0]] = current[0];
                }
            }
        }
    }

    public static void findRoute() {
        int current = end;
        route.add(current);

        while (current != start) {
            current = dest[current];
            route.add(current);
        }
    }
}