[백준 11404 파이썬] 플로이드 (골드 4, 플로이드 워셜)

알고리즘 유형 : 플로이드 워셜(최단 경로)
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input())
m = int(input())
cost_matrix = [[INF]*(n+1) for _ in range(n+1)]

# 제자리 사이클 0으로 초기화해주기
for i in range(1, n+1):
    cost_matrix[i][i] = 0

# 간선 정보 입력받아서 2차원 리스트에 저장
for _ in range(m):
    a, b, c = map(int, input().split())
    cost_matrix[a][b] = min(cost_matrix[a][b], c)

# 플로이드-워셜 알고리즘
def floyd_warshall(graph):
    costs = graph.copy()
    
    # 모든 노드에 대해, 각각이 중간 노드로서 반드시 임의의 경로에 포함될 때,
    # 그 때의 모든 노드로부터 노드로의 거리를 구하여 기존과 비교하여 갱신
    # 단방향 그래프이므로 각 중간 노드에 대해, 모든 노드에 대하여
    # n*n번 비교-갱신 해야됨. 그래서 시간 복잡도는 O(n^3)
    for mid_node in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                cal_cost = costs[i][mid_node] + costs[mid_node][j]
                if costs[i][j] > cal_cost:
                    costs[i][j] = cal_cost
                    
    return costs

result = floyd_warshall(cost_matrix)
line = ''
for i in range(1, n+1):
    line = ''
    for j in range(1, n+1):
        if result[i][j] != INF:
            line += str(result[i][j]) + " "
        else:
            line += "0 "
    print(line)

풀이 요약

1. 플로이드 워셜 알고리즘을 그대로 적용하면 되는 간단한 문제이다.

2. 모든 노드에서 모든 노드로의 최단 거리를 2차원 리스트로 표현한다. 입력을 받아 리스트를 초기화해주고, 간선이 존재하지 않는 노드와 노드의 경우에는 INF로 초기화. 단 i에서 i로 가는 경로(제자리 사이클)는 0으로 초기화해준다.

3. 플로이드 워셜 알고리즘은 DP 개념이 적용된 알고리즘이다.

   모든 노드에서 모든 노드로의 최단 거리를, 그 경로에 어떤 한 노드가 반드시 중간 노드로 포함된다고 가정하고, 그 때의 최단 거리를 구하여 기존과 비교 및 갱신해줌으로써 구해준다. 중간 노드를 모든 노드에 대해 각각 지정하여 갱신을 수행해주면, 마지막에 구해진 최단 경로 리스트는 모든 노드가 중간 노드인 경우를 모두 고려한 최단 경로이므로 이를 최단 거리로 확정지을 수 있다.

4. 이 문제는 단방향 그래프이므로, 각 중간 노드에 대해 1~n 노드에서 1~n 노드까지를 모두 비교 및 갱신해줘야한다.

   만약 양방향이면, 이중 for에서 i, j순으로 구성될 때, j를 i까지만 탐색해주면 된다. i와 j를 바꿔도 가중치가 같기 때문이다. 잘 생각해보면 이해가 될 것이다.

배운 점, 어려웠던 점

• 플로이드 워셜 알고리즘을 배우게 된 유용한 기초 문제였다.