[백준] 11404번 플로이드 (JAVA)

문제

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

11404번: 플로이드

 

설명

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구해야 한다.

모든 도시 쌍들 사이의 최단 경로를 구하는 방법으로는 플로이드-워셜 알고리즘이 있다.

i번째 도시에서 j번째 도시까지의 최소 비용을 저장할 costs[i][j] 배열을 만든다.

자기 자신은 0으로 채우고 나머지는 Integer.MAX_VALUE로 채운다.

// 자기 자신은 0으로 채우고 나머지는 Integer.MAX_VALUE로 채운다.
int[][] costs = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (i == j)
            costs[i][j] = 0;
        else
            costs[i][j] = Integer.MAX_VALUE;
    }
}

for 문을 3번 돌려서 모든 도시 쌍들 사이의 최소 비용을 구해야 한다. (전체 쌍 최단 경로)

costs[i][j] > costs[i][k] + costs[k][j] 일 경우 costs[i][j]를 갱신하는 방법을 취한다.

// for 문을 3번 돌려서 모든 도시 쌍들 사이의 최소 비용을 구한다 (전체 쌍 최단 경로)
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if ((i != j) && (costs[i][k] != Integer.MAX_VALUE) && (costs[k][j] != Integer.MAX_VALUE)) {
                if (costs[i][j] > costs[i][k] + costs[k][j]) {
                    costs[i][j] = costs[i][k] + costs[k][j];
                }
            }
        }
    }
}

 

전체 코드

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

public class Main {

    static int N, M;
    static int[][] costs;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        // 자기 자신은 0으로 채우고 나머지는 Integer.MAX_VALUE로 채운다.
        costs = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j)
                    costs[i][j] = 0;
                else
                    costs[i][j] = Integer.MAX_VALUE;
            }
        }

        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());

            if (costs[A][B] > C)
                costs[A][B] = C;
        }

        // for 문을 3번 돌려서 모든 도시 쌍들 사이의 최소 비용을 구한다 (전체 쌍 최단 경로)
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if ((i != j) && (costs[i][k] != Integer.MAX_VALUE) && (costs[k][j] != Integer.MAX_VALUE)) {
                        if (costs[i][j] > costs[i][k] + costs[k][j]) {
                            costs[i][j] = costs[i][k] + costs[k][j];
                        }
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (costs[i][j] == Integer.MAX_VALUE)
                    System.out.print(0 + " ");
                else
                    System.out.print(costs[i][j] + " ");
            }
            System.out.println();
        }
    }
}