[백준 / 골드4] 11404 플로이드 (Java)

플로이드 문제가 나올 때는 시간 복잡도가 O(V^3)이기 때문에 정점의 수가 100개 이하인 경우가 많다.

문제 보기

사용한 것

• 그래프의 모든 a, b 쌍에서 a -> b로 이동하기 위한 최소 비용을 구하기 위한 플로이드

풀이 방법

• 간선을 입력 받아 a -> b의 최소 비용을 저장한다.
• 모든 정점에 대해 -> i
  • 한 정점에서 -> j
    • 다른 한 정점으로 -> k
      • j -> k 보다 j -> i -> k가 더 최소 비용이면 교체한다.
      • 이 때 Integer.MAX_VALUE를 사용했으므로 오버플로우를 방지한다.
• 모든 a -> b에서 (a == b 가능) 도달할 수 없으면 0을 출력하고 도달할 수 있으면 최소 비용을 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());
        int[][] dist = new int[V + 1][V + 1];
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i == j) {
                    continue;
                }

                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        int E = Integer.parseInt(br.readLine());
        for (int i = 0; i < E; i++) {
            String[] line = br.readLine().split(" ");
            int from = Integer.parseInt(line[0]);
            int to = Integer.parseInt(line[1]);
            int cost = Integer.parseInt(line[2]);
            dist[from][to] = Math.min(cost, dist[from][to]);
        }

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 1; k <= V; k++) {
                    if (dist[j][i] != Integer.MAX_VALUE && dist[i][k] != Integer.MAX_VALUE) {
                        dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
                    }
                }
            }
        }

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

            System.out.println();
        }
    }
}