[BOJ] 백준 11404 플로이드

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

 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

플로이드 와샬 (Floyd Warshall)을 통해 구현할 수 있습니다.

플로이드 와샬 (Floyd Warshall)

『 i 』 → 『 i 』로 가는 경우에는 cost = 0

 

『 i 』 → 『 j 』 가는 최단거리 비용을 찾기 위해 정점 『 k 』를 추가하며 최단거리 비용을 갱신해줍니다.

 

정답을 출력할 때는 실제 연결되어 있지 않은 부분 『 INF 』 → 『 0 』으로 변환하여 출력합니다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static final int INF = 1000000;
    public static int N, M;
    public static int[][] dist;
     
    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];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                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);
        }
         
        // 플로이드 와샬 알고리즘
        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++) {
                    // 기존에 저장된 최단 거리와 정점 k를 거쳐가는 (i → k) + (k → j) 경로 중 최소값
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[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");
        }
        System.out.println(sb.toString());
    }
}