특정한 최단 경로

1504번: 특정한 최단 경로

🤔생각해보기

최단 경로 문제의 특정 조건이 포함된 응용 버전이다.

v1, v2 를 거쳐서 N 에 도달해야하는데 처음엔 v2 → v1 의 경우를 미처 고려하지 못해서 헤메다가 다른 분의 풀이에서 그 조건에 대한 통찰을 얻게 되어 해결할 수 있었다.

1. 시작점 → v1 → v2 → N
2. 시작점 → v2 → v1 → N

위 2가지 경우의 경로를 구하여 둘 중 작은 값을 출력한다.

코드

import sys
import heapq

N, E = map(int, sys.stdin.readline().split())
road = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

nodes = {}
for a, b, c in road:
    nodes[a] = nodes.get(a, []) + [(b, c)]
    nodes[b] = nodes.get(b, []) + [(a, c)]

v1, v2 = map(int, sys.stdin.readline().split())


def dijkstra(root, goal):
    dist = {i: float('inf') if i != root else 0 for i in range(1, N + 1)}

    heap = [(dist[root], root)]

    while heap:
        cur_dist, cur_node = heapq.heappop(heap)
        # dict key error 방지
        if not nodes.get(cur_node, []):
            continue

        for next_node, d in nodes[cur_node]:
            if dist[next_node] > dist[cur_node] + d:
                dist[next_node] = dist[cur_node] + d
                heapq.heappush(heap, (dist[next_node], next_node))

    return dist[goal]


path1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
path2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

result = min(path1, path2)
print(result if result < float('inf') else -1)

continue 처리는 딕셔너리에 존재하지 않는 키값을 호출할 경우 Key error 가 발생하는 것을 막기 위해 적어주었다.