[백준 11404번][Python] - 플로이드

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

 

# 풀이과정 (플로이드-워셜 알고리즘 이용)

1. N개의 도시를 하나씩, 순차적으로 중간 노드로 설정
2. 중간노드를 거쳐가는 경로가 기존 경로보다 짧으면 업데이트
3. 모든 도시를 대상으로 한 작업이 끝나면, 그 때의 거리가 최단 거리임
4. 최단거리 출력

 

[플로이드-워셜 알고리즘을 이용한 코드 - 성공]

# ex_11404
import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
distance = [[1e9 for _ in range(n)] for _ in range(n)]    # 거리를 저장하는 리스트

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    distance[a-1][b-1]=min(distance[a-1][b-1],c)

def floid(node):    # node:중간노드
    for start in range(n):
        if start==node:
            continue
        for end in range(n):
            if end==start or end==node:
                continue
            distance[start][end]=min(distance[start][node]+distance[node][end],distance[start][end])

for i in range(n):
    floid(i)

for i in range(n):
    for j in range(n):
        if distance[i][j] == 1e9:
            distance[i][j]=0

for row in distance:
    print(*row)

 

다익스트라 알고리즘이 특정 출발지에서 특정 목적지까지의 최단 경로를 구하는 반면에, 플로이드-워셜 알고리즘은 각 노드간의 최단거리를 구한다는 차이점이 있기에, 적절하게 활용해야함을 깨달았다.