[BOJ] 11404 : 플로이드 [그래프이론](Python)

문제 링크

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

11404번: 플로이드

소스 코드

import sys

def main():
    n = int(input())
    m = int(input())
    
    INF = int(1e9) # 초깃값
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

    for a in range(1,n+1):
        for b in range(1,n+1):
            if a == b: # 자기 자신으로 갈 때는 0
                graph[a][b] = 0

    for _ in range(m):
        a,b,c = map(int,sys.stdin.readline().strip().split())
        if c < graph[a][b]: # 기존 비용보다 작을 때만 업데이트
            graph[a][b] = c

    for k in range(1,n+1): # 중간 노드
        for a in range(1,n+1): # 출발 노드
            for b in range(1,n+1): # 도착 노드
                # 출발 - 도착 vs 출발 - 중간 - 도착
                graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

    for a in range(1,n+1):
        for b in range(1,n+1):
            if graph[a][b] == INF: # 이동 불가능한 경우
                print(0,end=' ')
            else:
                print(graph[a][b],end=' ')
        print() # 줄바꿈

if __name__ == '__main__':
    main()

 

해설

• 그래프 탐색, 그리디, 최단 경로, 플로이드 워셜

다익스트라 vs 플로이드 워셜

이 문제는 이름에서 알 수 있는 것처럼 플로이드 워셜 알고리즘을 적용하여 풀이하는 문제입니다.

최단 경로를 구하는 대표적인 알고리즘은 다익스트라와 플로이드 워셜이 있는데요, 둘의 차이점을 간단히 비교해보죠.

 

다익스트라는 힙을 이용하여 시작 노드로부터 도착 노드까지의 최단 경로를 구해줍니다.
현재 시점에서 이동할 수 있는 최소한의 비용이 드는 노드로 계속해서 이동하며 도착점까지 도달하게 되죠.

 

반면 플로이드 워셜은 모든 노드 간의 최소 비용을 구하게 됩니다.

따라서 출력해야 하는 값이 모든 노드 간의 비용임을 확인하고 이 문제는 플로이드 워셜로 접근하는 것이 맞습니다.

 

시간복잡도

그렇다면 이 알고리즘의 시간 복잡도는 어떻게 될까요?
이 알고리즘에서는 3중 for문을 사용하게 됩니다.

이때 각 for문의 범위는 노드의 개수 n까지 입니다.

따라서 시간 복잡도는 O(n^3)이 됩니다. 

 

문제 조건에 따라 n은 최대 100까지 이므로 100*100*100 = 1,000,000이 됩니다.

따라서 최악의 경우일지라도 시간 초과 판정을 받을 가능성이 낮다는 것을 알 수 있죠.

 

그래프 초기화

1)

우선 그래프를 초기화 할 때 INF를 설정합니다.

이는 이보다 큰 비용이 들지 않을 것임을 감안하고 세팅한 10억이라는 숫자입니다.

이후에 그래프에서 INF를 값으로 갖는 위치는 이동이 불가능한 케이스라는 것을 확인하기 위해 지정한 값이라고 이해하면 됩니다.

INF = int(1e9) # 초깃값
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

 

2)

자기 자신으로 이동할 때는 비용이 들지 않으므로 0으로 초기화합니다.

for a in range(1,n+1):
    for b in range(1,n+1):
        if a == b: # 자기 자신으로 갈 때는 0
            graph[a][b] = 0

 

3)

값을 입력으로 받을 때, 우리는 최소 이동 비용을 구해야 하므로, 기존 그래프에 저장된 값보다 작은 값이 들어올 때만 그래프를 업데이트 합니다.

실제로 문제의 예시에서는 같은 출발/도착 노드를 갖고 있지만 비용이 다른 경우가 존재합니다.

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    if c < graph[a][b]: # 기존 비용보다 작을 때만 업데이트
        graph[a][b] = c

 

3중 for문 설명

이 알고리즘은 그리디 유형에 속합니다.

3중 for문을 사용하는 이유는 '중간 노드'를 설정하기 위함입니다.

 

노드 a, b, k가 존재한다고 가정하겠습니다. 각각 출발, 도착, 중간 노드입니다.

때로는 노드 간 이동 비용에 따라 a에서 b로 바로 이동하는 것보다 다른 노드를 거쳐 가는 것이 더 경제적일 수 있습니다.

 

a -> b : 10

a -> k : 1

k -> b : 2

 

이동하는 비용이 위와 같다고 생각하면, a에서 b로 바로 이동하는 것보다 다른 곳을 거쳐가는 것이 낫겠죠.

그렇기 때문에 우리는 중간에 거쳐갈 수 있는 노드 k를 모두 뒤져봅니다.

요약하면, 'a->b' 비용과 'a->k' + 'k+b' 비용을 비교하여 더 작은 것을 취하는 거죠.

for k in range(1,n+1): # 중간 노드
    for a in range(1,n+1): # 출발 노드
        for b in range(1,n+1): # 도착 노드
            # 출발 - 도착 vs 출발 - 중간 - 도착
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

이처럼 min 함수를 사용하면 간단히 두 값을 비교하여 '최단 경로'를 구할 수 있게 됩니다.

 

마지막으로 출력하는 것은 각자 취향에 맞게끔 구현하시면 되겠습니다!