백준 - 11404번(플로이드)

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

문제

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 1. 플로이드 워셜
 * 2. 시간복잡도 -> 정점^3
 * 3. 변수 -> 뭔가 int로 가능할 것 같음
 * 4. 특이사항 -> 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
 */

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());    // 도시의 개수
        int m = Integer.parseInt(reader.readLine());    // 버스의 개수

        StringTokenizer tokenizer = null;

        int[][] city = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(city[i], Integer.MAX_VALUE);
            city[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            tokenizer = new StringTokenizer(reader.readLine());

            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());
            int weight = Integer.parseInt(tokenizer.nextToken());

            city[from][to] = Math.min(city[from][to], weight);
        }

        // i에서 j로 가는데 "k를 거쳐서" 간다!
        for (int k = 0; k <= n; k++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                    int temp = city[i][k] + city[k][j];
                    if (temp >= 0 && city[i][j] > temp) {
                        city[i][j] = temp;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sb.append(city[i][j] == Integer.MAX_VALUE ? 0 : city[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

}

• 플로이드 워셜 알고리즘을 학습하기 위한 기본적인 문제였다.
• 간단히 생각하면 바로 이해가 되는데, 뭔가 계속 보다보니 왜 최솟값을 보장하는지 잘 이해가 안되는 것 같다.