[백준] 11404번 - 플로이드 (Gold 4)

문제 링크

백준 11404번 - 플로이드 (Gold 4)

문제 설명

N개의 도시와 이들 도시 사이를 이동하는 M개의 버스가 있다.
각 버스의 출발지와 도착지, 비용이 주어져 있을 때 모든 도시의 쌍 (A, B)에 대해 도시 A에서 B로 가는데 필요한 최소 비용을 구하시오.

정답 코드 및 설명

전형적인 플로이드-워셜 알고리즘을 적용하는 문제이다.
플로이드-워셜 알고리즘은 백준 1956번 - 운동 (Gold 3)에서 설명하였다.
도시 A에서 도시 B로 가는 버스가 여러 대일 수 있음에 주의해야 한다.
아래 코드에서는 출발지와 도착지가 모두 같은 버스 중 최소의 비용을 가지는 버스만 저장했다.

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

public class BOJ11404 {
    static final int INF = 100000000;
    int n;
    int[][] bus;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        bus = new int[n][n];
        int m = Integer.parseInt(br.readLine());
        int start, end, cost;
        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            cost = Integer.parseInt(st.nextToken());
            if (bus[start][end] == 0 || cost < bus[start][end])
                bus[start][end] = cost;
        }
    }

    int[][] FloydWarshall() {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (bus[i][j] != 0) dist[i][j] = bus[i][j];
                else if (i != j) dist[i][j] = INF;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
        return dist;
    }

    void print(int[][] arr) throws IOException {
        for (int[] ints : arr) {
            StringBuilder sb = new StringBuilder();
            for (int anInt : ints) {
                int printValue = anInt;
                if (anInt == INF) printValue = 0;
                sb.append(printValue).append(' ');
            }
            System.out.println(sb);
        }
    }

    void solution() throws IOException {
        input();
        print(FloydWarshall());
    }

    public static void main(String[] args) throws IOException {
        new BOJ11404().solution();
    }
}