백준 - 11404 플로이드(Java)

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

11404번: 플로이드

 

문제 이름 그대로 플로이드 와샬(Floyd-Warshall)문제입니다.

플로이드 와샬이란, 각각의 정점에서 다른 정점으로 가는 경우의 최소를 구하는 알고리즘입니다.

가능한 모든 정점 2개의 조합에 대한 최단 경로를 구하는 알고리즘이기 때문에, All-Pairs(ASP)에 속합니다.

[시작 정점이 주어지는 다익스트라는 Single-Source(SSP)입니다.]

 

플로이드 와샬을 풀기 위해서는 노드의 개수 N을 입력 받아 이차원 배열(N*N)을 만들어야 합니다.

이 이차원 배열에서 모든 정점을 확인하기 위해서는 두 번의 반복문이 필요하기 때문에 O(N^2)의 시간 복잡도가 필요합니다.

게다가 돌아가는 경우가 더 짧을 수 있기 때문에 다른 노드를 체크하도록 반복문을 한번 더 써야 합니다.

즉, 플로이드 와샬의 최종적인 시간 복잡도는 O(N^3)이 됩니다.

// 노드 k를 거쳐 돌아가는 경우
for (int k = 1; k < n+1; k++) {
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < n+1; j++) {
            city[i][j] = Math.min(city[i][j],
                    city[i][k] + city[k][j]);
        }
    }
}

 

 

"시간 복잡도가 너무 큰거 아닌가?" 라는 의문이 들 수 있습니다.

일반적으로 탐색 알고리즘 문제를 풀다보면 O(N^2)조차 너무 오래걸리기 때문에,

보통 O(NlogN)정도 까지의 시간복잡도를 가지는 알고리즘으로 문제를 해결합니다.

 

하지만, 플로이드 와샬 문제에서 N은 크게 주어지지 않습니다.

플로이드 와샬의 N은 무엇일까요?

바로 노드의 개수입니다.

노드의 개수만 적게 주어진다면 충분히 플로이드 와샬을 도입할 수 있습니다.

 

다익스트라 시간 복잡도와 비교하겠습니다.

노드를 V 간선 E라고 할 때, 다익스트라의 시간복잡도는 O(VlogV + ElogV)입니다.

위에서 설명 했듯이, 플로이드 와샬의 시간복잡도는 O(V^3)입니다.

플로이드 와샬의 시간 복잡도는 간선의 개수와 관련이 없습니다.

 

예시 하나로 시간 복잡도를 각각 계산해 보겠습니다.

V = 128, E = 8000이라고 하면

다익스트라      : 128*(128*log(128) + 8000*log(128)) = 7,282,688

플로이드 와샬 : 128*128*128                                      =  2,097,152

입니다.

 

이러한 이유로, 플로이드 와샬은 노드의 개수만 적다면 충분히 사용할 수 있는 알고리즘인 것입니다.

 

백준의 11404에서는 노드의 개수가 문제에 주어지지 않았지만, 노드간의 모든 최소 가중치를 구해야하기 때문에 플로이드로 시도해 봐도 좋은 것 입니다. 아니면, 다익스트라를 노드의 개수만큼 반복을 해야하기 때문에 더 오래 걸려 시간초과가 발생할 수 있습니다.

 

[구현 코드]

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

public class Main {
	// Integer.MAX_VALUE는 알고리즘에 의해 범위를 넘어설 수 있으므로 사용해서는 안됨
    private static final int MAX = 999_999_999;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[][] city = new int[n+1][n+1];

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                city[i][j] = (i==j) ? 0 : MAX;
            }
        }

        for (int i = 0; i < m; i++) {
            stz = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

            // 문제 조건에 의해 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있으므로
            // 최소의 가중치를 갖는 노선 저장
            city[a][b] = Math.min(city[a][b], c);

        }

        for (int k = 1; k < n+1; k++) {
            for (int i = 1; i < n+1; i++) {
                for (int j = 1; j < n+1; j++) {
                    city[i][j] = Math.min(city[i][j],
                            city[i][k] + city[k][j]);
                }
            }
        }

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                // 갈 수 없는 경우 0을 출력
                int w = city[i][j] < MAX ? city[i][j] : 0;
                bw.write(w + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}