[백준] 11404: 플로이드

문제보기

이 문제는 플로이드-와샬 알고리즘을 이용해 모든 정점에 대한 최단거리를 구하는 문제였다.

플로이드 와샬 알고리즘은 다익스트라 알고리즘, 벨만 포드알고리즘처럼 원하는 특정 정점 쌍의 최단거리를 구하는 데가 아닌, 모든 정점에 대한 최단거리를 구할 때 이득이다. 이 알고리즘은 시간복잡도가 O(V^2)이당.

정점의 개수가 V, 간선의 개수가 E일 때, 다익스트라 알고리즘은 O(E*logV)(우선순위큐, 인접리스트 그래프로 최적화했을 때)이고, 벨만포드 알고리즘은 O(V*E) 이다. 근데 모든 정점에 대해서 연산해야한다고 하면 V를 한번 더 곱해준 O(VElogV), O(EV^2)가 되므로 플로이드 와샬보다 오래걸린다.

물~론 E가 크지 않은 이상 다익스트라 알고리즘이 더 좋을 수도 있긴하다. 하지만 다익스트라는 음수가중치가 있는 경우 사용할 수 없다는 단점이 있기 때문에 모든 정점 최단거리는 플로이드로!

파이썬 풀이

일단 cost배열 초기화 할 때 inf 값을 잘 설정해야한다. 아니면 나처럼

이 사단이 난다.

n의 최댓값은 100, m의 최댓값이 십만이므로 두 정점 사이 버스의 개수가 최댓값인 n-1이라고 생각하면 100*100000 쯤으로 예상할 수 있다. 난 처음에 m의 최댓값인 100000만 보다 크면 되는 줄 알았다. 그래서 inf 자리에 100001을 넣는 실수를 했다. 그러면 안된다..

import math
n = int(input())
m = int(input())
inf = math.inf
cost = [[inf]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if cost[a-1][b-1] > c:
        cost[a-1][b-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j and cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]
for row in cost:
    for col in row:
        if col == inf:
            print(0, end=' ')
        else:
            print(col, end=' ')
    print()

자바에서는 자료형과 범위가 정해져있으니까 그것만 따지면 되는데, 이번 문제에서는 inf를 int 범위로 정해도 무방해서 cost를 int 배열로 선언할 수 있었다.

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

public class Main { 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] cost = new int[n][n];
        int inf = 1000000000;

        // cost 배열 초기화
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++){
                if(i==j) {
                    cost[i][j] = 0;
                } else {
                    cost[i][j] = inf;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(cost[a-1][b-1] > c){
                cost[a-1][b-1] = c;
            }
        }

        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j<n; j++) {
                    if(cost[i][j] > cost[i][k] + cost[k][j])
                        cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(cost[i][j] == inf){
                    System.out.print(0+" ");
                }else {
                    System.out.print(cost[i][j]+" ");
                }
            }
            System.out.println();
        }
    }
}

주의할 점
1. 위에 썼듯, 최댓값 잘 유추하기
2. 파이썬은 n차원 배열 만들 때 깊은 복사를 위해서 for문 사용하기.
3. 3중반복문 사용시 k를 가장 바깥 부분에 해줘야 된다.