백준 9370 : 미확인 도착지 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(start,end):

    heap=[] ; heapq.heappush(heap,(0,start))
    dp=[INF]*(N+1)
    dp[start]=0

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            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)

for i in range(int(input())):

    N,M,T=map(int,input().split())

    S,G,H=map(int,input().split())

    graph=[ [] for _ in range(N+1) ] ; Answer=[]

    for j in range(M):
        a,b,d=map(int,input().split())
        graph[a].append((d,b))
        graph[b].append((d,a))


    for j in range(T):

        X=int(input())

        First = Dijkstra(S,G)+Dijkstra(G,H)+Dijkstra(H,X)
        Second = Dijkstra(S,H)+Dijkstra(H,G)+Dijkstra(G,X)

        Short = Dijkstra(S,X)
        if First==Short or Second==Short:
            Answer.append(X)

    Answer.sort()
    print(*Answer)

📌 어떻게 접근할 것인가?

문제 내용이 좀 어렵게 되어있는데 풀이자체는 간단합니다.

일단 시작점은 회색 노드입니다. 그리고 원하는 목적지는 검은 노드입니다.

이때 반드시 최단 경로로 이동해야합니다.

문제에서 원하는 것은 회색노드에서 검은노드로 이동했을때 점선을 지나는가? 입니다.

2번노드에서 6번노드의 최단경로는

• 2 - 1 - 3 - 6

위와같고 1 - 3 을 지나므로 , 즉 점선을 지나므로 6번노드는 정답이 됩니다
다만 2번노드에서 5번노드의 최단경로는

• 2 - 5

이므로 점선을 지나지 않으므로 5번노드는 정답이 아닙니다.
따라서 문제의 두번째 예제에 대한 출력값이 6 임을 알 수 있습니다.

First = Dijkstra(S,G)+Dijkstra(G,H)+Dijkstra(H,X)
Second = Dijkstra(S,H)+Dijkstra(H,G)+Dijkstra(G,X)

Short = Dijkstra(S,X)

총 3개의 다익스트라를 구현했습니다.

시작점이 $S$ 일때 $G$ 와 $H$ 를 지나고 $X$ 에 도달해야한다면

• $S$ - $G$ - $H$ - $X$
• $S$ - $H$ - $G$ - $X$

위 두가지 방법으로 이동가능하고

시작점에서 $X$ 로 다익스트라의 경로는

• $S$ - $X$

입니다.

이때 위의 최단경로의 값과 아래의 최단경로의 값이 같다면 , 최단경로로 이동하는 도중에 $G$ 와 $H$ 노드를 지났다는 의미이므로 정답이 됩니다.