[BOJ] 백준 11780 플로이드 2

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

 Input 

5

14

1 2 2

1 3 3

1 4 1

1 5 10

2 4 2

3 4 1

3 5 1

4 5 3

3 5 10

3 1 8

1 4 2

5 1 7

3 4 2

5 2 4

 

 Output 

0 2 3 1 4 
12 0 15 2 5 
8 5 0 1 1 
10 7 13 0 3 
7 4 10 6 0 
0
2 1 2 
2 1 3 
2 1 4 
3 1 3 5 
4 2 4 5 1 
0
5 2 4 5 1 3 
2 2 4 
3 2 4 5 
2 3 1 
3 3 5 2 
0
2 3 4 
2 3 5 
3 4 5 1 
3 4 5 2 
4 4 5 1 3 
0
2 4 5 
2 5 1 
2 5 2 
3 5 1 3 
3 5 2 4 
0

* 플로이드 와샬 (Floyd Warshall) 참고

플로이드 와샬 (Floyd Warshall)

 

구현

[BOJ] 11404 플로이드 문제에서 확장되어 경로를 추가적으로 구해야 합니다.

[BOJ] 백준 11404 플로이드

 

경로를 구하는 테이블 next[][] 초기화

① NIL = -1 로 정의

② 정점 u → 정점 v 일 때, 중간 정점없이 이동하는 경우 next[u][v] = u   

 

플로이드 와샬 알고리즘으로 최단거리 비용과 경로 테이블 도출

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    public static final int INF = 1000000;
    public static final int NIL = -1;
    public static int N, M;
    public static int[][] dist;
    public static int[][] next;
    public static Stack<Integer> path;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        N = Integer.parseInt(br.readLine());
        dist = new int[N + 1][N + 1];
        next = new int[N + 1][N + 1];
         
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                next[i][j] = NIL;
                if(i == j) continue;
                dist[i][j] = INF;
            }
        }
         
        M = Integer.parseInt(br.readLine());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            dist[u][v] = Math.min(dist[u][v], cost);
            next[u][v] = u;
        }
         
        // 플로이드 와샬 알고리즘
        floydWarshall();
         
        // 정답출력
        printAnswer();
    }
     
    public static void floydWarshall() {
        // 중간에 거쳐가는 정점 (k)
        for(int k = 1; k <= N; k++) {
            // 출발 정점 (i)
            for(int i=1; i <= N; i++) {
                // 도착 정점 (j)
                for(int j=1; j <= N; j++) {
                    if(dist[i][j] > dist[i][k] + dist[k][j]) {
                        // 기존에 저장된 최단 거리와 정점 k를 거쳐가는 (i → k) + (k → j) 경로 중 최소값
                        dist[i][j] = dist[i][k] + dist[k][j];
                        // 중간 경로로 정점 k를 거쳐가도록 갱신
                        next[i][j] = next[k][j]; 
                    }
                }
            }
        }
    }
     
    public static void printAnswer() {
        StringBuilder sb = new StringBuilder();
        // 최단 거리 비용
        for(int i=1; i <= N; i++) {
            for(int j=1; j <= N; j++) {
                if(dist[i][j] >= INF) sb.append("0 ");
                else sb.append(dist[i][j] + " ");
            }
            sb.append("\n");
        }
         
        // 최단 거리 경로
        for(int i=1; i <= N; i++) {
            for(int j=1; j <= N; j++) {
                // i == j로 자기자신이거나 i → j 가는 경로가 전혀 없는 경우
                if(next[i][j] == NIL) sb.append("0\n");
                else {
                    path = new Stack<>();
                    int pre = j;
                    path.add(j); // 거쳐가는 정점
                    while(i != next[i][pre]) { // 도착 정점까지
                        pre = next[i][pre];
                        path.push(pre);
                    }
                    // 최단 거리 경로 크기 (출발 정점까지 포함)
                    sb.append(path.size()+1 + " ");
                    sb.append(i + " ");
                    while(!path.empty()) {
                        sb.append(path.pop() + " ");
                    }
                    sb.append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}