[CLASS 4]백준 11404번 - 플로이드

11404번 : 플로이드

 

재미없게 문제 제목에서 어떤 알고리즘을 써서 풀어야 할지 스포일러 해버린 문제이다.

 

방향성이 있고 음의 간선이 없는 그래프에서 모든 정점에서 모든 정점까지의 최단거리를 구할 때는 플로이드 와샬 알고리즘을 사용한다.

 

이를 알고 있다면 아주 쉽게 풀 수 있는 문제이다. 구현도 어렵지 않다.

 

내 코드:

# dawitblog.tistory.com/165
from sys import stdin
input = stdin.readline

INF = 10_000_000
# 도시 수
n = int(input())

# 노선 비용 정보
cities = [[INF]*n for _ in range(n)]

# 입력
for _ in range(int(input())):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1

    cities[a][b] = min(cities[a][b],c)

# 플로이드-와샬
for v in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                cities[a][b] = min(cities[a][b],cities[a][v] + cities[v][b])

# 출력
for city in cities:
    print(*[i if i != INF else 0 for i in city])

 

플로이드 와샬 알고리즘은 그 유용성에 비해 정말 구현하기 쉬운 것 같다. 3중 for문 하나면 있으면 된다. 다만 주의할 점은 가장 바깥에 있는 변수(v)가 중간 경유지로 사용되어야 한다는 점이다.