[백준]1854 k번째 최단경로 찾기 #다익스트라

1. 풀이

어떤 node의 k번째 최단경로는 아래의 다익스트라구조에서 [구역1]에 해당하는부분에 k번째로 방문됐을때에 해당된다.

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

따라서 노드당 방문횟수를 저장하는 리스트(nodeCnt)와, k번째일때 해당 길이를 저장하는 리스트(ans)를 만들어 노드별 k번째 최단거리를 구하려고 했다. (소스코드1)

위 방법도 맞지만 문제가 있다. 바로 다익스트라를 언제 종료해야 하는지 처리하기가 어렵다.

다익스트라는 거리가 더 짧은 부분부터 탐색하기 때문에, a라는 노드를 100번방문해도, 거리에 따라서 b라는 노드에는 한번도 방문은 안할수도 있게 된다. 따라서 종료 조건을 설정하기가 애매하다.

​

따라서 그리드 bfs문제를 풀때처럼 다음 방문노드를 heapq에 넣기 전에 검사를 하는 방식을 이용했다.

이를 위해 힙을 원소로 가지는 kdist리스트를 관리한다

kDist[i] : i노드까지 갈 수 있는 경로중 짧은순으로 k개를 저장하는 힙

이후 다익스트라를 수행하며 아래와 같은 경우로 나누어 처리를 한다.

  (1) a노드가 k번 방문되지 않았을때 : kdist에 추가.

  (2) a노드가 k번 방문 되었고 kDist[a]의 가장 큰 숫자보다 현재경로가 짧을때 : kdist[a]에서 가장 큰 숫자 빼고 현재 경로 추가

  (3) a노드가 k번 방문 되었고 kDist[a]의 가장 큰 숫자보다 현재경로가 더 길때 : 통과

​

위와같이 처리를 하면, 자동으로 kDist[a]의 가장 큰 숫자가 k번째 최단거리가 된다.

또한 kDist[a]의 원소가 k개이면, kDist[a]와 연결된 노드들에도 k번 방문되었음이 보장되기 때문에(소스코드1 방법과 달리 다음 노드를 탐색하면서 kDist에 넣어주었기 때문에) kDist에서 가장큰 숫자보다 더 큰숫자에 대해서는 탐색을 안해줘도 된다. 즉 우선순위큐 (dij)속 원소의 존재여부를 이용하여 종료조건을 만들 수 있다.

​

2. 소스코드

(1) 소스코드1 (무한반복)

import heapq
import sys
INF=9876543210
n,m,k=map(int,input().split())
graph={}
for i in range(n+1):
    graph[i]=[]
for i in range(m):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append([b,c])

nodeCnt=[0 for i in range(n+1)]
ans=[-1 for i in range(n+1)]
nodeDist=[INF for i in range(n+1)]
dij=[[0,1]]
while(dij):
    print(ans)
    nowCost,nowNode=heapq.heappop(dij)
    # nodeCnt[nowNode]번째 최단거리임
    nodeCnt[nowNode]+=1
    nodeDist[nowNode] = nowCost
    # k번째면 기록
    if nodeCnt[nowNode]==k:
        ans[nowNode]=nowCost

    for toNode,addedCost in graph[nowNode]:
        toCost=nowCost+addedCost
        heapq.heappush(dij,[toCost,toNode])

 

(2) 소스코드2 (통과)

import heapq
import sys
INF=9876543210
n,m,k=map(int,input().split())
graph={}
for i in range(n+1):
    graph[i]=[]
for i in range(m):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append([b,c])

kDist=[[] for i in range(n+1)]
kDist[1].append(0)
nodeDist=[INF for i in range(n+1)]
dij=[[0,1]]
while(dij):
    nowCost,nowNode=heapq.heappop(dij)
    for toNode,addedCost in graph[nowNode]:
        toCost=nowCost+addedCost
        if len(kDist[toNode])<k:
            heapq.heappush(kDist[toNode],-toCost)
            heapq.heappush(dij,[toCost,toNode])
        elif kDist[toNode][0]<-toCost:
            heapq.heappop(kDist[toNode])
            heapq.heappush(kDist[toNode],-toCost)
            heapq.heappush(dij,[toCost,toNode])

for i in range(1,n+1):
    if len(kDist[i])!=k:
        print(-1)
    else:
        print(-kDist[i][0])