[백준] 11404번 : 플로이드 (Python)

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

 

import sys

input = sys.stdin.readline

V = int(input()) # 도시 개수
E = int(input()) # 노선 개수

distance = [[sys.maxsize for _ in range(V+1)] for _ in range(V+1)] # 인접 행렬
    
# 노선 데이터를 distance 행렬에 저장
for i in range(E):
    s, e, v = map(int, input().split())

    if distance[s][e] > v: # 노선이 여러개일 때, 작은 노선만 저장
        distance[s][e] = v

# 플로이드-워셜 알고리즘 수행
for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):

            if(i==j): # 시작 도시와 종료 도시가 같은 자리에 0 저장!
                distance[i][i] = 0
                continue
            
            distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j]) # 거리 업데이트
            
# 최단 거리 print
for i in range(1, V+1):
    for j in range(1, V+1):
        if distance[i][j] != sys.maxsize:  # 갈 수 있는 도시인 경우
            print(distance[i][j], end=' ')
            
        else:  # 갈 수 없는 도시의 경우
            print(0, end=' ')
    print()

 

 

[문제풀이]

---

 

이 문제는 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구해야 한다.

즉, 플로이드-워셜 알고리즘을 사용해야 한다!

 

1. 인접 행렬에 시작 도시와 도착 도시를 연결하는 노선 저장
2. 플로이드-워셜 점화식을 사용해 알고리즘을 수행
3. 인접 행렬 출력

 

위와 같은 3단계로 문제를 풀면 된다.

 

distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j]) # 거리 업데이트

 

플로이드 워셜 점화식은 이렇다.

모든 k를 거쳐가는 최단경로를 다 뒤져본 다음 짧은 애를 선택!