[JAVA] 백준 11404 - 플로이드

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

플로이드-워셜 알고리즘은 N개의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘으로, I->J까지의 거리가 최단 거리라면 부분 경로인 I -> K 와 K-> J의 경로도 최단 거리라는 사실에 기반을 뒀다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int cNum = Integer.parseInt(s);
        int lNum = Integer.parseInt(br.readLine());
        int[][] map = new int[cNum][cNum];
        int inf = 99999999;
        for (int i = 0; i < map.length; i++) {
            Arrays.fill(map[i], inf);
            map[i][i] = 0;
        }
        for (int i = 0; i < lNum; i++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map[arr[0] - 1][arr[1] - 1] = Math.min(arr[2], map[arr[0] - 1][arr[1] - 1]);
        }

        for (int k = 0; k < cNum; k++) {
            for (int i = 0; i < cNum; i++) {
                for (int j = 0; j < cNum; j++) {
                    if (map[i][k] + map[k][j] < map[i][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

        for (int i = 0; i < cNum; i++) {
            for (int j = 0; j < cNum; j++) {
                if(map[i][j]==inf) map[i][j] = 0;
            }
        }
        for (int i = 0; i < cNum; i++) {
            System.out.println(Arrays.toString(map[i]).replaceAll("[^0-9 ]",""));
        }
    }
}

I -> J 경로의 개수가 1개가 아닐 수 있으므로 경로의 최솟값만 세팅해주고 3중 for문을 통해 map[i][j]보다 작은 경유 경로를 찾는다.

따라서 시간복잡도는 O(n^3)이라 정점의 갯수가 많은(10만개 등) 경우 적절한 방법이 아니다.

 

다익스트라는 특정 정점으로부터 다른 모든 정점까지의 최단거리를 구하는 탐욕법에 기반한 알고리즘이고, 이번에 구현한 플로이드 워셜은 모든 정점에서부터 다른 모든 정점까지의 최단거리를 구하는 동적계획법에 기반한 알고리즘이다.