[백준] 1854번 - K번째 최단경로 찾기

---

문제 분석

시작점과 도착점이 주어지고 해당 목적지까지 가는 K번째 최단경로를 구하는 문제이다.
K번째 최단 경로를 해결하기 위해서는 다음과 같은 아이디어로 접근하면 된다.

1. 최단 경로를 표현하는 리스트를 K개의 row를 갖는 2차원 리스트의 형태로 변경하고자 한다. 이렇게 하면 최단 경로뿐만 아니라 최단 경로 ~ K번째 최단 경로까지 표현할 수 있다.
2. 기존 다익스트라 로직에서 사용한 노드를 방문 리스트에 체크해 두고 다음 도착 시 해당 노드를 다시 사용하지 않도록 설정하는 부분은 삭제가 필요하다. k번째 경로를 찾기 위해서는 노드를 여러번 쓰는 경우가 생기기 때문이다.

또한 추가로, 최단 거리 리스트를 채우는 경우에는 다음과 같은 규칙을 적용하여 채우면 된다.

1. 우선순위 큐에서 연결된 노드와 가중치 데이터를 가져온다
2. 연결 노드의 K번째 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 업데이트한다. 이때 경로가 업데이트되는 경우, 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가한다.
3. 1~2단계를 우선순위 큐가 비워질 때 까지 반복한다. K번째 경로를 찾기 위해 노드를 여러 번 방문하는 경우가 있으므로 기존 다익스트라의 방문 노드를 체크하여 재사용하지 않는 로직은 구현하지 않는다.

---

소스 코드

# K번째 최단경로 찾기

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
arr = [[] for _ in range(N + 1)]
temp = [[sys.maxsize for j in range(K)] for i in range(N + 1)]
temp[1][0] = 0
queue = PriorityQueue()

for _ in range(M):
    start, end, value = map(int, input().split())
    arr[start].append((end, value))

queue.put((0, 1))

while not queue.empty():
    routeValue, nextNode = queue.get()
    for v in arr[nextNode]:
        if routeValue + v[1] < temp[v[0]][K - 1]:
            temp[v[0]].append(routeValue + v[1])
            temp[v[0]].sort()
            queue.put((routeValue + v[1], v[0]))

for i in range(1, N + 1):
    if temp[i][K - 1] == sys.maxsize:
        print(-1)
    else:
        print(temp[i][K-1])