[백준] 11780번 - 플로이드 2 (Gold 2)

문제 링크

백준 11780번 - 플로이드 2 (Gold 2)

문제 설명

n(1 $\leq$ n $\leq$ 100)개의 도시가 있다.
이 도시 사이를 잇는 m(1 $\leq$ m $\leq$ 100,000)개의 버스 각각의 출발지와 도착지, 비용이 주어진다.
모든 도시의 쌍 (A, B)에 대해 도시 A에서 도시 B로 가는데 드는 최소의 비용과 그 경로를 출력하시오.
만약 도시 A에서 도시 B로 갈 수 없거나, A = B이면 0을 출력한다.

정답 코드 및 설명

플로이드-워셜 알고리즘을 사용하는 전형적인 문제이다.
플로이드-워셜 알고리즘은 각 경로에서 가능한 중간 경유지의 후보를 늘려가는 식으로 진행되는 알고리즘이다.
따라서, 각 경로의 중간 경유지를 따로 저장해둔다면 역으로 경로를 복구해낼 수 있다.
중간 경유지가 없이 직접 가는 경우를 구분할 필요가 있는데, 아래 코드에서는 중간 경유지 값으로 -1을 저장했다면 직접 이동하는 것이 가장 비용이 싼 경로라는 뜻이다.
플로이드-워셜 알고리즘과 중간 경유지 저장은 코드의 60행 ~ 67행을 참고하면 된다.

경로를 복구해내는 과정을 살펴보자.
출발지와 도착지를 알고 있다면, 경유지도 위에서 저장해두어서 알고 있다.
따라서 출발지 - 경유지 - 도착지의 구조가 형성된다.
이제 출발지 - 경유지의 경로와 경유지 - 도착지의 경로를 각각 복구해서 합쳐주면 전체 경로가 된다.
여기서 만일 각 경로에 출발지와 도착지를 모두 포함시켜둔다면 경로를 합칠 때 이 점들은 두 번 들어가게 된다.
따라서, 아래 코드에서는 출발지와 도착지를 뺀 중간 지점들만 경로에 저장하고, 경로를 합치는 과정에서 경유지를 중간에 더해주며, 마지막에 출력할 때 출발지와 도착지를 처음과 끝에 추가하는 방식을 택하였다.
자세한 과정은 코드의 86행 ~ 105행을 참고하면 된다.

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

public class BOJ11780 {
    static final int INF = 1_000_000_000;

    int n;
    int[][] bus;
    Cost[][] minCost;
    Path[][] path;

    static class Cost {
        int cost;
        int intermidiate;

        Cost(int cost, int intermidiate) {
            if (cost == 0) this.cost = INF;
            else this.cost = cost;
            this.intermidiate = intermidiate;
        }
    }

    static class Path {
        int length;
        String path;

        Path(int length, String path) {
            this.length = length;
            this.path = path;
        }
    }

    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 int[n][n];
        minCost = new Cost[n][n];
        path = new Path[n][n];
        StringTokenizer st;
        int start, end, cost;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            cost = Integer.parseInt(st.nextToken());
            if (bus[start][end] == 0 || cost < bus[start][end])
                bus[start][end] = cost;
        }
    }

    void initializeMinPath() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                minCost[i][j] = new Cost(bus[i][j], -1);
            }
        }
    }

    void FloydWarshall() {
        initializeMinPath();
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (minCost[i][k].cost + minCost[k][j].cost < minCost[i][j].cost) {
                        minCost[i][j].cost = minCost[i][k].cost + minCost[k][j].cost;
                        minCost[i][j].intermidiate = k;
                    }
                }
            }
        }
    }

    String printMinCost() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || minCost[i][j].cost == INF) sb.append(0).append(' ');
                else sb.append(minCost[i][j].cost).append(' ');
            }
            sb.append('\n');
        }
        return sb.toString();
    }

    Path traceback(int i, int j) {
        if (path[i][j] != null) return path[i][j];
        if (i == j || minCost[i][j].cost == INF)
            return path[i][j] = new Path(-1, "");
        if (minCost[i][j].intermidiate == -1)
            return path[i][j] = new Path(1, " ");
        int k = minCost[i][j].intermidiate;
        Path ik = traceback(i, k);
        Path kj = traceback(k, j);
        return path[i][j] = new Path(ik.length + kj.length,
                ik.path + (k + 1) + kj.path);
    }

    String printPath(int i, int j, Path path) {
        StringBuilder sb = new StringBuilder();
        sb.append(path.length + 1);
        if (path.length > 0) {
            sb.append(' ').append(i + 1).append(path.path).append(j + 1);
        }
        return sb.toString();
    }

    void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(printMinCost());
        bw.flush();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bw.write(printPath(i, j, traceback(i, j)));
                bw.newLine();
                bw.flush();
            }
        }
        bw.close();
    }

    void solution() throws IOException {
        input();
        FloydWarshall();
        print();
    }

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