[백준/Python]11404: 플로이드

문제

https://www.acmicpc.net/problem/11404
백준 문제집 - 0x1C강 - 플로이드 알고리즘

 

알고리즘: 최단 경로, 플로이드-워셜

---

풀이

정말 기초적인 플로이드 워셜 문제다.

 

플로이드-워셜 알고리즘?

최단경로를 구하는데에 사용하는 알고리즘 중 하나다. (+ 다익스트라, 벨만-포드)
다른 두 개는 한 정점에서 다른 모든 정점까지의 최단거리를 찾지만, 플로이드 워셜은 모든 정점 쌍 간의 최단경로를 한번에 계산한다. (그리고 음의 가중치도 계산 가능)

 

원리는 DP와 비슷하다.
정점 i에서 정점 j로 가는 경로 중,정점 k를 경유하는 경로가 더 짧다면 👉 최단 경로 갱신

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

그리고 모든 정점 k에 대해 위 과정을 반복하면서 갱신해나간다.

 

전체 코드

# 최단 경로

# 플로이드-워셜 알고리즘 문제
# 한 노드에서 모든 노드까지가 아닌, 모든 노드간의 최단거리를 구할 수 있는 알고리즘이다.
# 시작노드가 i, 도착노드가 j일때 노드 k를 거쳐가는 경우를 확인한다. dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])


# 메모리: 42140KB / 시간: 376ms
from sys import stdin


input = stdin.readline
INF = int(1e9)
n = int(input())
N = n + 1
m = int(input())

bus = []
for _ in range(m):
    bus.append(tuple(map(int, input().split())))

def floyd_warshall():
    dp = [[INF]*(N) for _ in range(N)]

    for i in range(1, N):  # 자기 자신으로 가는 비용은 0으로 설정한다.
        dp[i][i] = 0

    for u, v, w in bus:  # 시작-끝이 같은 노선이 여러 개 있을 수 있기 때문에 최소값인 노선으로 설정하도록 한다.
        dp[u][v] = min(dp[u][v], w)

    for k in range(1, N):  # 거치는 부분
        for i in range(1, N):  # 시작점
            for j in range(1, N):  # 끝점
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp

ret = floyd_warshall()

for i in range(1, N):
    for j in range(1, N):
        if ret[i][j] == INF:
            ret[i][j] = 0
    print(*ret[i][1:])