[백준/Python]1719: 택배

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 최단 경로, 데이크스트라, 플로이드-워셜

---

풀이

최단경로를 구해야 하니 플로이드 워셜은 필수고, 추가로 경로표(다음에 방문할 노드)도 구해야 한다.
(11780: 플로이드 2를 풀어봤다면 쉬운 문제다.)

 

먼저 최단경로용 리스트 / 경로 저장용 리스트를 따로 생성해야 한다.
각 리스트는 다음과 같이 구성 될 예정이다.
graph[a][b]: a에서 b로 가는 최단거리
nxt[a][b]: a에서 b로 갈 때, a 다음으로 방문할 노드

 

(a, b)가 같은 중복 데이터는 주어지지 않으니 입력 데이터 그대로 리스트에 저장해주면 된다.

graph[a][b] = c
nxt[a][b] = b

 

그리고 플로이드 워셜을 수행하면서 경로표를 갱신해준다.
만약 a-b 루트보다 a-k + k-b 루트가 더 효율적이라면 a 다음에 nxt[a][k] 노드로 가야 한다.

if graph[a][b] > graph[a][k] + graph[k][b]:
    graph[a][b] = graph[a][k] + graph[k][b]
    nxt[a][b] = nxt[a][k]

 

이런식으로 갱신하다보면 nxt[a][b]에는 "a 방문 후, 바로 다음으로 방문해야 할 노드"가 저장될것이다.

👇이해가 잘 안될경우 아래의 질문글을 참고해보면 좋을것같다.
https://www.acmicpc.net/board/view/104174

 

전체 코드

# 메모리: 33432KB / 시간: 584ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

def main():
    N, M = map(int, input().split())
    graph = [[INF] * N for _ in range(N)]
    nxt = [[-1] * N for _ in range(N)]

    for _ in range(M):
        u, v, w = map(int, input().split())
        graph[u-1][v-1] = w
        graph[v-1][u-1] = w

        nxt[u-1][v-1] = v
        nxt[v-1][u-1] = u

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    nxt[i][j] = nxt[i][k]

    for i in range(N):
        line = ["-" if i == j else nxt[i][j] for j in range(N)]
        print(*line)


main()