[백준] 11780번 - 플로이드 2 [Java]

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

 

[백준] 11780번 - 플로이드 2 [Java]

[백준] 11780번 - 플로이드 2 [Java]

---

1.  아이디어

 

이전 플로이드 문제에서 경로 출력까지 추가된 문제로 최단 거리를 갱신할 때 방문한 경유지 정보를 기록하는 before 배열을 활용하면 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 11404번 - 플로이드 [Java])

---

2. 문제풀이

 

경로 입력 단계에서 before 배열을 초기화한 후 3중 반복문에서 경유지를 방문한 경로가 더 짧을 경우 dp 테이블 갱신 후 before 배열에서 before[i][j] = before[k][j]로 i에서 j로 가기 위한 경로에 k에서 j로 가는 경로를 저장해줬다. 이후 이를 역순으로 조회하면 경로를 얻을 수 있고 출력을 위해 Stack 자료구조와 StringBuilder를 활용했다.

---

3. 코드

 

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

public class Main {

    private static final int INF = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        int[][] dp = new int[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], INF);
            dp[i][i] = 0;
        }

        int[][] before = new int[1 + N][1 + N];

        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());

            if (dp[A][B] > C) {
                dp[A][B] = C;
                before[A][B] = A;
            }
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dp[i][j] > dp[i][k] + dp[k][j]) {
                        dp[i][j] = dp[i][k] + dp[k][j];
                        before[i][j] = before[k][j];
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dp[i][j] == INF) sb.append("0 ");
                else sb.append(dp[i][j]).append(" ");
            }
            sb.append("\n");
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dp[i][j] == INF || i == j) sb.append("0\n");
                else sb.append(find(i, j, before[i][j], before));
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static String find(int start, int end, int cur, int[][] before) {
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(end);
        while (cur != 0) {
            stack.push(cur);
            cur = before[start][cur];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(stack.size()).append(" ");
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }
        sb.append("\n");

        return sb.toString();
    }

}

---

4. 후기