BOJ 1854 k번째 최단경로 찾기

다익스트라 알고리즘을 이용하는데, 최단 경로를 찾을 때는 현재까지 찾은 가장 짧은 경로들을 prioirty_queue(max heap이지만 min heap처럼 사용해야 함)에 넣고, 빼면서 최단 경로들을 확정해 나갔다면, k번째 최단 경로를 찾기 위해서는 가장 짧은 경로들만 구하는 것이 아니라 만들어지는 경로는 다 구하되, 그 중 크기 순으로 k개의 경로를 구하는 것이다.

그래서 원래 다익스트라 알고리즘에서는 각 정점까지의 최단 거리를 저장하고 있었다면, 이 문제에서는 각 정점까지의 k개이하의 거리를 저장하고 있어야 한다. 각 정점까지의 k개이하의 거리를 저장하는 것도, k개이하의 최단거리를 저장해야 하므로, 일단, 저장된 거리의 수가 k개 미만이면 새로 발견한 거리를 저장하고, 만약 k개가 꽉 찼다면 그 중 가장 큰 거리와 비교해서 새로 발견한 거리가 더 작다면 갱신해주는 식으로 나가야 하는데, 가장 큰 거리를 찾는데 좋은 자료구조가 바로 max heap이다. priority_queue를 쓰면 될 것이다.

한 번 나도 풀어봐야겠다.
처음에는 WA를 받고, dist[1].push(0)을 추가하고 AC를 받았다.
문제를 대충 읽어서, 그리고 예제만 보고 i부터 i는 0이 아닌 것으로 생각했는데, 문제를 다시 읽어보니 i에서 i로의 k번째 경로가 0이 아닐 수 있다고 주의하라는 것이었을 뿐...
그리고 이 문제에서는 원래 다익스트라에서 처럼 결정된 경로에 대해서는 따로 check배열을 만들어서 두 번 이상 확인하지 않도록 했던 것처럼 어떤 조건을 따로 명시하지는 않고 그냥 했다. 시간이 좀 더 빠른 코드들을 보면 조건을 넣고 더이상 안보도록 continue를 해주는 부분이 삽입되어 있는데, 유카리코(yukariko)님 코드를 보면 pq에서 꺼낸 점점까지의 거리의 수가 k개이고, 그 중 최대 거리가 pq에서 같이 꺼낸 거리보다 작다면 continue를 해준 것으로 보이는데, 즉 pq에서 꺼낸 것보다 더 나은, 해당 정점까지의 k개의 최단 경로가 있는 경우에는 pq에서 꺼낸 것을 쓸 필요 없다는 것을 의미하는 것 같다. 왜냐하면 이미 해당 점점까지의 k개의 최단 경로를 이용해서 다음 정점들까지의 각각 k개의 거리를 얻는 작업을 했을 것이기 때문이다.

참고 : 백준님 문제풀이 강의, 강의 자료.