[BOJ 1719] 택배 (Python)

풀이

처음에는 다익스트라 알고리즘을 사용해 모든 최단 경로를 구한 후 거쳐가는 직전의 집하장을 저장하는 방식으로 접근했다. 그러나 구현이 어려워 헤맸다. 따라서 플로이드 워셜 알고리즘을 사용하여 문제를 풀었다.

플로이드 워셜 알고리즘을 사용한 이유는 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 했기 때문에 사용하였다. 또한, 플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3)인데 문제에서 N은 최대 200으로 200 x 200 x 200 = 8,000,000으로 플로이드 워셜을 사용할 이유는 충분하다고 판단했다.

문제의 포인트는 최단 거리 정보를 저장하는 2차원 리스트 1개와 경로표를 저장하는 2차원 리스트 1개 총 2개의 리스트를 사용하는 것이라고 생각한다. 플로이드 워셜 알고리즘이 동작하는 부분에서 기존의 저장된 최단 거리보다 더 작은 최단 거리가 발견되면 거리와 집하장 정보를 갱신한다. 이때 집하장은 앞의 집하장으로 갱신해야 한다. 왜냐하면 문제에서 원하는 답의 형태이기 때문이다.

1. 최단 거리 정보와 거쳐 가는 집하장의 정보를 각각 리스트에 저장

2. 플로이드 워셜 알고리즘을 사용한다.

   • 기존의 저장된 거리보다 더 최단 거리가 발견되면 발견된 최단 거리로 갱신
   • 이후 발견된 최단 거리의 경로에서 앞의 집하장으로 집하장 정보를 갱신

3. 플로이드 워셜 알고리즘이 종료되면 집하장 정보를 저장한 2차원 리스트를 출력

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
INF = int(1e9)

graph = [[INF] * (N + 1) for _ in range(N + 1)]
ans = [[0] * (N + 1) for _ in range(N + 1)]

for a in range(N + 1):
    for b in range(N + 1):
        if a == b:
            graph[a][b] = 0
            ans[a][b] = INF

for _ in range(M):
    v1, v2, route = map(int, input().split())
    # 양방향 그래프이므로
    graph[v1][v2] = route
    graph[v2][v1] = route
    # v1 출발 -> v2 도착이면 v1 기준으로 v2가 도착지점이 되어야함.
    ans[v1][v2] = v2
    # 위와 반대
    ans[v2][v1] = v1

# 플로이드 워셜 알고리즘 (점화식 이용 --> DP)
for k in range(1, N + 1):
    for a in range(1, N + 1):
        for b in range(1, N + 1):
            # 기존의 a -> b로 가는 저장된 비용보다
            # a -> k -> b로 가는 경로가 더 최단 거리이면
            if graph[a][b] > graph[a][k] + graph[k][b]:
                # 비용을 최단 거리로 갱신
                graph[a][b] = graph[a][k] + graph[k][b]
                # 먼저 들러야하는 지점인 (a, k)의 집하장 값으로 갱신
                ans[a][b] = ans[a][k]

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