[백준-파이썬] 1719: 택배

문제 보러 가기!

모든 지점에서 모든 지점까지 가는 최소 비용(최단 경로)을 구해야 하므로 플로이드 와샬 알고리즘을 썼다.
일반적인 플로이드 와샬과 다르게, 최소 비용 자체가 정답이 아니라, 최소 비용이 되기 위해서는 어디를 가장 먼저 방문해야 할지를 구하는 문제였다.
그래서 이동할 때 드는 최소 비용을 저장한 2차원 리스트에 더해서, 최소 비용이 되려면 어디를 가장 먼저 방문해야 하는지 저장하는 2차원 리스트(move)도 만들었다.
그리고 플로이드 와샬 알고리즘을 사용하면서, i 에서 j 지점으로 가는데 k를 들러서 가는 게 최소 비용이라면 ! 비용을 갱신하면서, 가장 먼저 방문할 지점도 업데이트해줬다.

틀렸던 이유

• 양방향인데 단방향으로 생각해서 ㅠ
• 자기 자신으로 갈 때 처음 방문할 지점을 '-'로 해서(i로 하고, 나중에 출력할 때 자기 자신이면 '-'로 출력해야 한다.)
• 가장 먼저 방문할 지점 업데이트할 때, move[i][k]로 안하고 그냥 k로 해서

코드

import sys

INF = 987654321
input = sys.stdin.readline
n, m = map(int, input().split())
move = list([0] * (n + 1) for _ in range(n + 1))  # 어디를 가장 먼저 방문해야 할지
dist = list([INF] * (n + 1) for _ in range(n + 1))  # 이동할 때 드는 최소 비용

for _ in range(m):
    start, end, time = map(int, input().split())
    dist[start][end] = time  # 경로가 있는 경우 초기화
    dist[end][start] = time
    move[start][end] = end
    move[end][start] = start

# 자기 자신으로 가는 것 0으로 초기화
for i in range(1, n + 1):
    move[i][i] = i
    dist[i][i] = 0

for k in range(1, n + 1):  # 거쳐가는 점
    for i in range(1, n + 1):  # 출발점
        for j in range(1, n + 1):  # 도착점
            if dist[i][j] > (dist[i][k] + dist[k][j]):  # 업데이트 되어야 한다면
                dist[i][j] = dist[i][k] + dist[k][j] # 비용 갱신
                move[i][j] = move[i][k] # 가장 먼저 방문할 지점 바꾸기

for i in range(1, n + 1):
    for j in range(1, n+1):
        if i == j:
            print('-', end=' ')
        else:
            print(move[i][j], end=' ')
    print()