https://www.acmicpc.net/problem/1162
문제 요약
N개의 도시, M개의 도로가 주어지며, 두 도시를 잇는 각 도로는 지나는 데 걸리는 시간이 있다.
이때 K개의 도로를 포장할 수 있다. 도로를 포장하면 해당 도로의 소요 시간이 0이 된다.
이러한 상황에서 1번 도시에서 출발해 N번 도시에 도달하는 최소 시간을 얻어라.
도시의 개수 N은 최대 1만이다.
도로의 수 M은 최대 5만이다.
포장할 수 있는 도로의 수 K는 최대 20이다.
각 도로를 지나는 데 걸리는 시간은 최대 100만이다.
문제 접근
먼저 전체 걸리는 시간의 최댓값을 생각하면, 도로가 1만개이고 각 도로의 소요 시간이 100만이기 때문에 int의 범위인 20억을 넘을 수 있다. 따라서 long을 사용해야 한다.
문제를 단순하게 생각하면 시작점에서 도착점에 도달할 수 있는 모든 경로를 얻고, 각 경로에서 가장 시간이 큰 K개의 도로를 제거해서 시간을 구하면 되겠지만, 모든 경로를 구한다는 것부터 시간, 공간, 구현적으로 말이 안 된다.
결국 최단 거리를 얻는 알고리즘 중 하나를 사용해야 하는데, 도시의 개수와 도로의 수의 최댓값을 고려하면 의 복잡도를 갖는 다익스트라 알고리즘을 사용해야 한다는 점을 느낄 수 있다.
다만 K개 도로의 비용을 0으로 만들면서 최단 거리를 구하는 것은 고민이 된다.
다익스트라 알고리즘으로 얻은 최단 경로에서 시간이 큰 K개의 도로를 제거하는 것은 최단 경로가 아닐 수 있다. 이는 문제에서 주어진 예시에서 바로 확인할 수 있다.
그러면 어떻게 해야할까?
정답은 DP를 함께 활용하는 것이다.
가로는 노드의 번호, 세로는 무시할 도로의 수를 나타내는 배열을 생각해보자.
그러면 특정 개수의 도로를 무시했을 때 해당 노드에 도달할 수 있는 최단 거리를 배열을 통해 얻을 수 있다.
이 배열은 무시할 도로의 수를 1씩 증가시키며 한 줄씩 채워나가면 된다.
무시하는 도로의 수가 0일 때는 다익스트라 알고리즘을 한 번 사용하면 배열이 채워진다.
무시하는 도로의 수가 1일 때부터는 이전 값을 함께 사용해야 한다.
예를 들어 시작점에서 A 도시를 거쳐 B 도시로 간다고 할 때, 도로를 1개 무시해서 갈 수 있는 최단 경로는 A와 B 사이의 도로를 무시하는 경우와 무시하지 않는 경우(즉, 이미 다른 도로를 무시한 경우) 중 더 작은 값이 된다.
이를 코드 형태로 표현하면 dist[1][5] = Math.min(dist[0][3], dist[1][3] + (3와 5 사이의 거리))이다.
결국 다익스트라 알고리즘을 K번 사용해서 문제를 해결할 수 있다.
유의할 점
K개의 도로를 무시할 수 있다고 해서 정확히 K개 도로를 무시할 필요는 없고, K개 이하만 무시하면 된다.
풀이
기본적인 아이디어는 다음과 같다.
- 도로를 입력받아 양방향 그래프를 구성한다.
- 무시하는 도로에 수에 따른 각 노드의 최단 거리를 기록하는 배열을 만든다.
- 다익스트라 알고리즘을 사용하여 배열을 한 줄 씩 채운다. 이는 직전 줄의 값을 사용하게 된다.
- 각 무시하는 도로 수에 대해 도착점에 도달할 수 있는 최단 거리가 정답이 된다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static final long INF = 1000000000000000000L;
static int N, M, K;
static ArrayList<int[]>[] graph;
static long[][] distances;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N, M, K 입력 받기
StringTokenizer st1 = new StringTokenizer(br.readLine());
N = Integer.parseInt(st1.nextToken());
M = Integer.parseInt(st1.nextToken());
K = Integer.parseInt(st1.nextToken());
// graph의 크기를 설정하고, 각 인덱스의 arraylist를 선언한다.
graph = new ArrayList[N+1];
for (int i = 0; i < N+1; i++) {
graph[i] = new ArrayList<>();
}
// 엣지를 입력받아 그래프 구성하기 - 양방향임을 기억
for (int i = 0; i < M; i++) {
StringTokenizer stm = new StringTokenizer(br.readLine());
int A = Integer.parseInt(stm.nextToken());
int B = Integer.parseInt(stm.nextToken());
int C = Integer.parseInt(stm.nextToken());
int[] leftNext = new int[] {B, C}; // {다음 노드 번호, 거리}
int[] rightNext = new int[] {A, C}; // {다음 노드 번호, 거리}
graph[A].add(leftNext);
graph[B].add(rightNext);
}
// 시작점과의 최단 거리를 기록하는 배열
// 세로축 인덱스는 포장할 수 있는 도로의 개수, 가로축은 노드 번호
distances = new long[K+1][N+1];
for (int i = 0; i < K+1; i++) {
for (int j = 0; j < N+1; j++) {
distances[i][j] = INF;
}
}
// 다익스트라 알고리즘을 위한 자료구조 선언
// 시작점과의 거리를 오름차순으로 하는 우선순위 큐(각 다익스트라에서 계속 재활용할 것이다)
PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>() {
@Override
public int compare(long[] o1, long[] o2) { // {노드 번호, 시작점과의 거리}
return Long.compare(o1[1], o2[1]);
}
});
// 방문 여부 확인 배열(각 다익스트라에서 계속 재활용할 것이다)
boolean[] isVisited = new boolean[N+1];
for(int i = 0; i < N+1; i++) {
isVisited[i] = false;
}
// 먼저 다익스트라를 한 번 수행해서 최단 거리 배열의 첫번째 줄을 채운다.
int startPoint = 1;
distances[0][startPoint] = 0;
long[] start = new long[] {startPoint, 0};
pq.add(start);
while (!pq.isEmpty()) {
long[] now = pq.poll(); // {노드 번호, 시작점과의 거리}
if (isVisited[(int) now[0]]) continue;
isVisited[(int) now[0]] = true;
for (int[] next : graph[(int) now[0]]) { //{노드 번호, now[0]과의 거리}
if (isVisited[next[0]]) continue;
distances[0][next[0]] = Math.min(distances[0][next[0]], now[1] + next[1]);
long[] updatedNext = new long[] {next[0], distances[0][next[0]]};
pq.add(updatedNext);
}
}
//System.out.println(Arrays.toString(distances[0]));
// 다익스트라를 K번 수행해서 모든 배열을 채운다.
for (int i = 1; i <= K; i++) {
// 사용할 자료구조를 초기화한다.
pq.clear();
for(int j = 0; j < N+1; j++) {
isVisited[j] = false;
}
distances[i][startPoint] = 0;
pq.add(start);
while (!pq.isEmpty()) {
long[] now = pq.poll(); // {노드 번호, 시작점과의 거리}
if (isVisited[(int) now[0]]) continue;
isVisited[(int) now[0]] = true;
for (int[] next : graph[(int) now[0]]) { //{노드 번호, now[0]과의 거리}
if (isVisited[next[0]]) continue;
long originDist = distances[i][next[0]]; // 기존 거리
long ignoreNewEdge = distances[i-1][(int) now[0]]; // now와 next 사이의 엣지를 무시하는 거리
long ignoreFormerEdge = distances[i][(int) now[0]] + next[1]; // now에 올 때 이미 엣지를 무시한 거리
distances[i][next[0]] = Math.min(originDist, Math.min(ignoreNewEdge, ignoreFormerEdge));
long[] updatedNext = new long[] {next[0], distances[i][next[0]]};
pq.add(updatedNext);
}
}
}
// 여태 구한 값 중 최소가 정답이 된다
long answer = INF;
for (int i = 0; i < K+1; i++) {
answer = Math.min(answer, distances[i][N]);
}
System.out.println(answer);
}
}회고
온전히 내 생각으로 푼 문제는 아니고, 2차원 배열 DP를 사용한다는 힌트를 기반으로 문제를 해결할 수 있었다.
틀렸던 이유
도로를 K개 포장할 수 있다고 해서 꼭 K번 모두 포장하여 도착점에 도달하는 값이 최단 경로가 아닐 수 있다.
왜냐하면 최단 경로에서 거치는 도로의 수가 K개보다 적어서 도로를 K번 거치면 도착점에 도달할 수 없는 경우가 있기 때문이다.
문제 예시에서 K가 3으로 주어지는 경우가 이러한 경우에 해당한다. 시작점에서 도착점까지 도로를 2개 거치는데, 도로 3개의 값을 무시하고 이동하면 도착점이 아닌 노드에 도달하게 된다.
