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

접근

문제 풀이에 앞서 플로이드 와샬 알고리즘이 무엇인지 공부해보았다.

이전에 풀었던 다익스트라 알고리즘이 하나의 점에서 출발했을 때 모든 정점까지의 최단 경로를 구했다면, 플로이드 와샬 알고리즘은 모든 점에서 모든 점까지의 최단 경로를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는것이다.

문제의 예제 입력에 주어진 버스 노선을 그래프로 표시하면 아래와 같다. (중복되는 버스 경로는 최소값만 저장)

그리고 이를 n * n 크기의 표로 표시하면 아래와 같다.

0	2	3	1	10
INF	0	INF	2	INF
8	INF	0	1	1
INF	INF	INF	0	3
7	4	INF	INF	0

이 표는 현재까지 계산된 최소 이동비용이다. 이 표를 계속 갱신하여 최종적으로 모든 정점 사이의 최소 이동 비용을 구해야 한다. 위의 표에는 현재 하나의 버스 노선을 타고 직접 이동하는 경우만 저장되어 있다. 이제 각 노드들을 거쳐가는 경로를 이용하여 표를 갱신해준다.

1번 노드를 거쳐가는 경우, 아래의 노란색으로 표시된 칸들에 대하여

1. X에서 Y로 바로 이동
2. X에서 1을 거쳐서 Y로 이동

두가지를 비교하여 더 작은 값으로 수정해주면 된다.

0	2	3	1	10
INF	0	INF	2	INF
8	INF	0	1	1
INF	INF	INF	0	3
7	4	INF	INF	0

이러한 연산을 모든 노드들에 거쳐서 반복 수행해주면 표의 각 값이 최소 이동 비용을 표시하게 된다.

코드

import sys

INF = float('inf')
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
s = [[INF] * (n + 1) for i in range(n + 1)]

for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if s[a][b] > c:
        s[a][b] = c

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j and s[i][j] > s[i][k] + s[k][j]:
                s[i][j] = s[i][k] + s[k][j]

for i in s[1:]:
    for j in i[1:]:
        if j == INF:
            print(0, end=' ')
        else:
            print(j, end=' ')
    print()

더 생각해 볼 것?

처음 알게되는 알고리즘을 알기 쉽게 설명하기가 쉽지 않은 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!