[골드 3] 백준 1719 - 택배 (파이썬)

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

분류 : 다익스트라

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

풀이

이 문제는 어느 경로로 가는 것이 최단 경로인지를 알아내는 문제이다.

각 도시(정점) 간의 최단 경로를 찾아야하며, 단순히 최단 거리만 출력하는 것이 아니라, 어디로 먼저 가야 하는지를 출력해야한다.

즉, i → j 로 갈 때 첫번째로 가야하는 도시를 출력해야하는 것ㅇ디ㅏ.

from queue import PriorityQueue

N, M = map(int, input().split())  # 도시 수 N, 도로 수 M
adj = [[] for _ in range(N)]      # 인접 리스트

# 간선 정보 입력
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1            # 0-indexed
    adj[a].append((b, c))
    adj[b].append((a, c))

# 모든 정점쌍 최단 거리 저장할 2차원 리스트
dist = [[1e9] * N for _ in range(N)]

# 모든 정점에 대해 다익스트라 수행
for s in range(N):
    pq = PriorityQueue()
    pq.put((0, s))
    dist[s][s] = 0

    while pq.qsize() != 0:
        d, u = pq.get()
        if d != dist[s][u]:
            continue

        for v, w in adj[u]:
            if dist[s][v] > dist[s][u] + w:
                dist[s][v] = dist[s][u] + w
                pq.put((dist[s][v], v))

for i in range(N):
    for j in range(N):
        if i == j:
            print("-", end=" ")
        else:
            for k, w in adj[i]:
                if dist[i][j] == w + dist[k][j]:
                    print(k + 1, end=" ")
                    break
    print()

의도는 i → j 로 가는 최단 경로에서 처음으로 가야 할 노드 k를 찾고 싶은 것이다. i → k 간선이 있고, k → j까지 최단 거리라면 그게 최단 경로 일까?

이 방식은 단순한 거리 비교에 기반하고 있다.

dist[i][j] == w + dist[k][j] 조건을 만족하는 아무 노드나 찍는다.

하지만 최단 경로는 여러 개일 수도 있고, 경유 순서를 추적하지 않기 때문에 반례가 존재한다.

예시 반례를 다음과 같다.

1 -> 2-> 4, 1 -> 3 -> 4 둘다 거리가 2

근데 adj[1]에 2, 3 모두 연결되ㅓ 있고, dist[1][4] == w + dist[k][4] 조건을 만족한다.

어떤 걸 먼저 print 할지는 adj[1] 순서에 따라 달라진다.

항목 설명

장점	다익스트라를 N번 돌려서 모든 쌍의 최단 거리를 구함
문제점	최단 거리만 있고, 경로(특히 첫 번째 경유지) 추적을 하지 않음
오답 가능성	단순한 거리 비교로는 정확한 경로 추정이 안 됨 (정점 방문 흐름이 보장되지 않음)

일단은 코드가 맞았지만, 개선 방법을 요약하면 다음과 같다.

• 다익스트라 수행 중에 이 정점은 어디를 통해 처음 왔는가를 기록해야 한다.
• 즉, first[s][v] = u 또는 first[s][v] = first[s][u] 방식으로 추적이 필요하다.

코드

# 백준 1719 - 택배
# 분류 : 다익스트라

from queue import PriorityQueue

N, M = map(int, input().split())
adj = [[] for _ in range(N)]

for _ in range(M) :
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    adj[a].append((b, c))
    adj[b].append((a, c))

dist = [[1e9] * N for _ in range(N)]

for s in range(N) :
    pq = PriorityQueue()

    pq.put((0, s))
    dist[s][s] = 0

    while pq.qsize() != 0 :
        d, u = pq.get()
        if d != dist[s][u] :
            continue

        for v, w in adj[u] :
            if dist[s][v] > dist[s][u] + w :
                dist[s][v] = dist[s][u] + w
                pq.put((dist[s][v], v))

for i in range(N) :
    for j in range(N) :
        if i == j :
            print("-", end = " ")
        else :
            for k, w in adj[i] :
                if dist[i][j] == w + dist[k][j] :
                    print(k + 1, end = " ")
                    break
        
    print()