백준 11404 자바 - 플로이드

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

11404번: 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] array = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    array[i][j] = 0;
                } else {
                    array[i][j] = 987654321;
                }
            }
        }

        StringTokenizer st;
        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());
            array[a][b] = Math.min(array[a][b], c);
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (array[i][j] > array[i][k] + array[k][j]) {
                        array[i][j] = array[i][k] + array[k][j];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (array[i][j] == 987654321) {
                    array[i][j] = 0;
                }
                sb.append(array[i][j]).append(" ");
            }
            sb.append("\n");
        }

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

풀이

 플로이드 워셜 알고리즘을 통해 풀어야 한다. 예를 들어 a, b, c의 지점이 있고, a -> c의 경로와 a -> b, b -> c의 경로가 있을 경우, a -> c의 경로의 길이와 a -> b, b -> c 의 경로의 길이의 합을 비교해 더 짧을 경우를 a 에서 c로 가는 경로의 길이로 저장하여 모든 경로를 계산해 짧은 거리를 계산하는 것이다. 위 문제에서는 갈 수 없는 경우에 0으로 출력해야하는 부분만 조심하면, 나머지 부분은 플로이드 워셜로 해결할 수 있다.