백준 11780번: 플로이드 2 (Python)

접근

기존에 풀었던 플로이드 기본문제와 같이 플로이드 와샬 알고리즘을 이용하여 풀 수 있다. 다만 새로운 리스트를 작성하여 직전 도시를 저장해주면 된다.

플로이드 와샬 알고리즘 설명 및 기본 문제: 2021.04.21 - [코딩/백준 (Python)] - 백준 11404번: 플로이드 (Python)

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

기존 문제에서 어떤 코드가 추가되었는지 코드를 보면서 설명하도록 하겠다.

코드

import sys

INF = float('inf')
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
dp = [[INF] * (n + 1) for _ in range(n + 1)]
prev = [[0] * (n + 1) for _ in range(n + 1)]  # prev[i][j]에는 i에서 j로 갈 때, j 도착 직전 위치를 저장해준다.
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if dp[a][b] > c:
        dp[a][b] = c
        prev[a][b] = a  # a에서 b로 갈 때, b 도착 직전 위치는 a 이므로 코드와 같이 저장

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 dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
                prev[i][j] = prev[k][j]  # 경로를 갱신해줄 때 직전 위치도 같이 갱신해준다.

for i in dp[1:]:
    tmp = []
    for j in i[1:]:
        if j == INF:
            tmp.append(0)
        else:
            tmp.append(j)
    print(*tmp)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if dp[i][j] == INF:  # i에서 j로 도착하지 못할 경우
            print(0)
        else:
            route = [j]  # 경로 저장 임시 리스트
            tmp = j
            while tmp != i:  # 시작점까지 탐색
                route.append(prev[i][tmp])
                tmp = prev[i][tmp]
                # prev[i][tmp]에는 i ~ tmp 경로 중 직전 위치가 저장되어 있다.
                # 이 직전 위치를 계속 따라가다 시작점에 도달하면 순환이 끝난다.
            print(len(route), end=' ')
            print(*route[::-1])  # 저장된 루트를 reverse해서 출력한다.

더 생각해 볼 것?

...

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