문제
그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.
그림 1
예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.
어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 용의자는 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 경찰이 검문을 위하여 선택하는 도로에 따라서 용의자의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다.
문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다.
- 두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다.
- 도시의 지점(노드)은 1에서 N번까지 N개의 연속된 정수로 표시된다.
- 용의자가 도시에 진입하는 지점은 항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다.
- 용의자는 검문을 피해서 가장 빨리 도시를 빠져나가고자 하고, 경찰은 적절한 도로를 선택하여 이 용이자들의 탈출시간을 최대한 지연시키고자 한다.
- 각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다.
입력 도시의 도로망에 따라서 경찰이 어떤 도로를 막으면 용의자는 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다.
그림 1에서 볼 때 검문이 없을 경우 용의자가 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 경찰이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 용의자들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다.
여러분은 입력 데이터에 표시된 도로망을 읽고, 경찰이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다.
입력
첫 줄에는 지점의 수를 나타내는 정수 N(6 <= N <= 1000)과 도로의 수 M(6 <= M <= 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 <= t <= 10000이다.</p>
출력
경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)
풀이
모든 도로를 하나씩 막아 보며 다익스트라를 돌리면 맞긴 하지만, 꼭 그럴 필요는 없다. 실제로 영향을 줄 수 있는 도로는 처음 최단 경로 위에 있는 간선들뿐이다.
코드에서는 먼저 다익스트라를 한 번 실행해 원래 최단 거리와 함께 parent[]를 저장한다. 이 parent[]는 최단 경로 트리를 따라 N에서 1로 되짚어 올라갈 수 있게 해준다.
그 다음에는 원래 최단 경로에 포함된 간선만 하나씩 막아 가며 다시 다익스트라를 실행한다. 어떤 간선을 막았는데도 다른 우회 경로가 있으면 지연 시간을 갱신하고, 아예 도달할 수 없으면 답은 곧바로 -1이다.
핵심은 "최단 경로에 없던 간선을 막아도 원래 최단 시간은 변하지 않는다"는 점이다. 그래서 첫 최단 경로를 역추적한 뒤 그 위의 간선만 검사해도 충분하다.
코드
import java.util.*;
import java.io.*;
public class Main {
static class Node implements Comparable<Node> {
int end, weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.weight, o.weight);
}
}
static ArrayList<Node>[] graph;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N + 1];
graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++)
graph[i] = new ArrayList<>();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, t));
graph[b].add(new Node(a, t));
}
for (int i = 1; i <= N; i++)
Collections.sort(graph[i]);
int originalMinTIme = solve(N, -1, -1);
int curNode = N;
int maxDelay = 0;
while (curNode != 1) {
int prevNode = parent[curNode];
int blockedTime = solve(N, prevNode, curNode);
if (blockedTime == Integer.MAX_VALUE) {
System.out.println(-1);
return;
}
maxDelay = Math.max(maxDelay, blockedTime - originalMinTIme);
curNode = prevNode;
}
System.out.println(maxDelay);
}
static int solve(int N, int blockA, int blockB) {
int[] dist = new int[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(1, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (dist[cur.end] < cur.weight) continue;
for (Node next : graph[cur.end]) {
if ((cur.end == blockA && next.end == blockB) ||
(cur.end == blockB && next.end == blockA))
continue;
if (dist[next.end] > dist[cur.end] + next.weight) {
dist[next.end] = dist[cur.end] + next.weight;
pq.offer(new Node(next.end, dist[next.end]));
if (blockA == -1)
parent[next.end] = cur.end;
}
}
}
return dist[N];
}
}복잡도
- 시간 복잡도:
P는 원래 최단 경로에 포함된 간선 수
- 공간 복잡도:
마무리
핵심은 모든 도로를 막아보는 게 아니라, 처음 최단 경로를 만든 도로들만 다시 보는 것이다. 최단 경로 계산과 역추적을 연결하면 브루트포스를 꽤 많이 줄일 수 있다.
