백준 1504 : 특정한 최단 경로 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(node,end):
    heap = []
    heapq.heappush(heap,(0,node))
    dp = [INF] * (N + 1)
    dp[node]=0

    while heap:

        value,node=heapq.heappop(heap)

        if value<dp[node] and node!=v_1 and node!=v_2:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:

                dp[next_node]=next_value

                heapq.heappush(heap,(next_value,next_node))
    return dp[end]



INF=int(1e9)
N,E=map(int,input().split())

graph=[ [] for _ in range(N+1) ]
for i in range(E):
    a,b,c=map(int,input().split())
    graph[a].append((c,b)) # 가중치 먼저
    graph[b].append((c,a))

v_1,v_2=map(int,input().split())

path1=Dijkstra(1,v_1)+Dijkstra(v_1,v_2)+Dijkstra(v_2,N)
path2=Dijkstra(1,v_2)+Dijkstra(v_2,v_1)+Dijkstra(v_1,N)

if min(path1,path2)>=int(1e9):
    print(-1)
else:
    print(min(path1,path2))

📌 어떻게 접근할 것인가?

다익스트라 응용 문제입니다. 아주 중요하다고 생각되는 문제입니다.

문제에서 요구하는 바는 최단경로를 구하는 것이지만 , 이때 특정 두 노드를 꼭 방문해야 합니다.

따라서 1부터 $N$ 까지 간다고 했을때 $A$ 와 $B$ 라는 정점을 지나야 한다면

• 1 - $A$ - $B$ - $N$
• 1 - $B$ - $A$ - $N$

위와 같은 경로로 이동가능합니다.

또한 다익스타라는 꼭 1번부터 $N$ 번까지 이동할 필요는 없으므로 1번부터 $A$ 번까지의 최단경로와 1번부터 $B$ 번까지의 최단경로를 각각 구해준후에 그때의 합을 구해주면 문제에서 요구하는 바를 총족할 수 있습니다.

매우 중요한 응용이므로 꼭 기억해야합니다.