백준 11404 - 플로이드 (Python3)

코드

n = int(input())
m = int(input())

INF = int(1e9)
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 비용 0
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0
         
        
# 간선 간의 연결 정보 및 이동 비용 입력    
for _ in range(m):
    a, b, c = map(int, input().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):
            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):
        
        # 도달할 수 없으면 0
        if graph[a][b] == INF:
            print(0, end = ' ')
        else:
            print(graph[a][b], end = ' ')
        
    print()                    

문제 해설

전형적인 플로이드 워셜 알고리즘 문제이다.

최단 경로 알고리즘 중 비교적 간단하게 해결할 수 있는 알고리즘으로 DP의 원리를 이용하여 거쳐가는 노드를 기준으로 최단 거리 테이블을 갱신하는 방식으로 동작한다.