[백준]9370 미확인도착지 #다익스트라 정석

1. 풀이

가중치 있는 그래프이므로 일반적인 다익스트라 알고리즘을 사용하면 되는데, 특정 경로를 지났는지를 확인해주어야 한다.

다익스트라는 아래와 같이 구성된다.

while(dij):
   nowDist,nowNode,isCon=heapq.heappop(dij)
   if nodeDist[nowNode]<nowDist:
      <이미 방문되었는지 확인부분>
   [구역1]
   for toNode,cost in graph[nowNode]:
      <새로 연결될것을 찾는부분>
      [구역2]

(1) [구역2]에서 현재 노드와 연결된 노드들을 찾는다. 이때 가중치들이 최신화된다.

(2) [구역1]은 pq(heap)에 의해서 가중치가 가장 작은 노드가 뽑혀져 나온 후, 이미 방문되었는지 필터를 거친상태이다. 이때 다익스트라의 중요한 특징이 있다. 바로 [구역1]에서는 항상 nowNode가 처음으로 방문된, 가장 최단거리를 구한 순간의 상태가 되는것이다. (즉 [구역1]은 항상 노드수만큼 거치게 된다)

따라서 노드별로 최단거리를 구한 순간 반드시 거쳐야 하는 경로를 거쳤는지 확인하려면 [구역1]에서 해주어야 하는 것이다. 따라서 구역1에서 isConnected[nowNode]=1을 해준다.

* 처음엔 [구역2]에서 해줬는데 이러면 아직 최단경로가 아닌 지점에서 isConnected가 수정되므로 답이 틀리게 된다

​

2. 소스코드

import heapq
maxNum=9876543210

T=int(input())
for _ in range(T):
    n,m,t=map(int,input().split())
    s,g,h=map(int,input().split())
    graph={}
    for i in range(1,n+1):
        graph[i]=[]
    for i in range(m):
        a,b,d=map(int,input().split())
        graph[a].append([b,d])
        graph[b].append([a,d])
    dest=[]
    for i in range(t):
        dest.append(int(input()))
    dest.sort()

    isConnected=[0 for i in range(n+1)] #g-h 간선을 지났으면 1
    dij=[[0,s,0]]
    nodeDist=[maxNum for i in range(n+1)]
    nodeDist[s]=0
    while(dij):
        nowDist,nowNode,isCon=heapq.heappop(dij)
        if nodeDist[nowNode]<nowDist:
            continue
        if isCon:
            isConnected[nowNode]=1
        for toNode,cost in graph[nowNode]:
            addedDist=nowDist+cost
            if addedDist<=nodeDist[toNode]:
                nodeDist[toNode]=addedDist
                if isCon or [nowNode,toNode] in [[g,h],[h,g]]:
                    heapq.heappush(dij,[addedDist,toNode,1])
                else:
                    heapq.heappush(dij,[addedDist,toNode,0])

    #print(nodeDist)
    #print(isConnected)
    ans=[]
    for i in dest:
        if isConnected[i]:
            ans.append(i)
    print(*ans)