문제
N개의 도시와 M개의 단방향 간선으로 이루어진 그래프에서, 1번 도시에서 각 도시까지의 K번째 최단 경로의 길이를 구하는 문제다. 최단 경로가 아닌 K번째로 짧은 경로를 모두 구해야 하므로, 각 도시마다 최대 K개의 경로 길이를 관리해야 한다.
입력
- 첫째 줄: 도시의 수 N, 간선의 수 M, K (1 ≤ N ≤ 1000, 0 ≤ M ≤ 2000000, 1 ≤ K ≤ 100)
- 둘째 줄부터 M개의 줄: 간선 정보
u v w(도시 u에서 v로 가는 가중치 w인 간선)
출력
N개의 줄에 걸쳐 1번 도시에서 i번 도시로 가는 K번째 최단 경로의 길이를 출력한다. K번째 경로가 존재하지 않으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 10 2 1 2 2 1 3 7 1 4 5 1 5 6 2 4 2 2 3 4 3 5 5 4 5 3 4 3 6 5 4 1 | 1 -1 9 5 10 |
풀이
다익스트라(Dijkstra) 알고리즘을 변형하여, 각 도시마다 도착한 경로 길이를 최대 K개 관리하는 방식으로 K번째 최단 경로를 구한다. 일반 다익스트라에서 dist[v] > new_cost이면 갱신하는 것과 달리, 이 문제에서는 각 도시에 도달한 비용을 K개까지 모아두고, K번째보다 작은 경로가 새로 발견될 때만 갱신한다.
- 각 도시
dist[i]를 크기 K의 **최대 힙(max-heap)**으로 초기화한다. - 시작 도시 1번에서 비용 0으로 다익스트라를 시작한다.
- 현재 노드에서 인접 노드로 이동하는 비용
new_cost를 계산한다. - 인접 노드의 힙 크기가 K 미만이면
new_cost를 힙에 추가하고 큐에 삽입한다. - 힙 크기가 K이고 힙의 최댓값이
new_cost보다 크면, 최댓값을 제거하고new_cost를 삽입한다 (더 짧은 경로로 교체). - 탐색 종료 후 각 도시의 힙에 K개의 원소가 있으면 최댓값(K번째 최단 경로)을 출력, 아니면 -1을 출력한다.
핵심 아이디어: 각 노드마다 최대 힙으로 K번째 최단 거리를 관리한다. 힙의 최댓값이 현재 K번째 후보이며, 더 짧은 경로가 나타날 때만 힙을 갱신함으로써 K번째 최단 경로를 효율적으로 추적한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day65BOJ1854K번째최단경로Dijkstra { // 1854 K번째 최단경로
static final int INF = 1 << 30;
static int N, M, K;
static PriorityQueue<Integer>[] dist;
static List<int[]>[] list;
static PriorityQueue<int[]> pq;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken()); // 도시
M = Integer.parseInt(st.nextToken()); // 간선
K = Integer.parseInt(st.nextToken()); // K번째 최단 경로
dist = new PriorityQueue[N + 1]; // 최소힙 관리
list = new ArrayList[N + 1];
pq = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
for (int i = 1; i < N + 1; i++) {
dist[i] = new PriorityQueue<>(); // 최단 경로가 아닌, K번째 찾기
list[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list[p].add(new int[] { c, w });
}
pq.add(new int[] { 1, 0 }); // 1번 마을, 누적합 0
dist[1].add(0); // 1번 마을에 최소힙으로 경로 쌓기
while (!pq.isEmpty()) {
int[] cur = pq.poll();
for (int[] next : list[cur[0]]) {
if (dist[next[0]].size() < K) {
dist[next[0]].add((cur[1] + next[1]) * -1);
pq.add(new int[] { next[0], cur[1] + next[1] });
} else if (dist[next[0]].peek() * -1 > cur[1] + next[1]) {
dist[next[0]].poll();
dist[next[0]].add((cur[1] + next[1]) * -1);
pq.add(new int[] { next[0], cur[1] + next[1] });
} // K개 빼고는 버리고, pq에 추가
}
}
for (int i = 1; i < N + 1; i++) {
if (dist[i].size() == K)
sb.append(dist[i].peek() * -1).append("\n");
else
sb.append(-1).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(K * (V + E) log(KV)) — 각 노드에 최대 K번 방문 가능하므로 일반 다익스트라 대비 K배
- 공간: O(KV + E) — 각 노드마다 K개의 경로를 저장