https://www.acmicpc.net/problem/5719
문제 요약
거의 최단 경로는 최단 경로의 도로를 포함하지 않는 경로 중 가장 짧은 경로를 의미한다.
최단 경로가 여러 가지인 경우에도 모든 도로를 포함하지 않아야 한다.
또한, 거의 최단 경로는 여러 개 존재하거나 없을 수도 있다.
입력은 여러 개의 테스트 케이스로 주어지며, 입력의 마지막 줄에는 0이 두개 주어진다.
각 테스트 케이스에서 사용되는 변수는 다음과 같다.
장소의 수 N은 최대 500이다.
도로의 수 M은 최대 10000이다.
시작 장소 S와 도착 장소 D가 주어진다.
도로의 정보는 출발점, 도착점, 길이의 순으로 주어지며, 이는 단방향 도로를 의미한다.
이때 거의 최단 경로의 길이를 구하여라.
만약 거의 최단 경로가 없는 경우에는 -1을 출력한다.
문제 접근
단순하게 생각하면, 다익스트라 알고리즘을 두 번 사용해서 문제를 해결할 수 있을 것 같다.
- 첫번째 다익스트라에서는 최단 거리의 도로를 기록하여 제거한다.
- 두번째 다익스트라에서는 단순히 최단 거리를 구한다. 이 결과가 거의 최단 경로가 된다.
하지만 문제가 그렇게 쉽게 해결되지는 않는다.
고민점 1: 다익스트라 알고리즘으로 진행한 경로를 어떻게 기록하지?
일반적으로 다익스트라 알고리즘은 단순히 최단 경로의 길이만을 기록하지만, 위에서 이야기한 첫번째 다익스트라의 역할을 고려하면 지나온 경로를 기록하여 이를 제거할 수 있어야 한다.
이를 위해서는 해당 장소 직전에 방문한 장소를 기록하면 된다.
즉, 다익스트라 알고리즘으로 특정 장소에 도달했다면 그때 사용한 도로의 시작점을 함께 기록해서 추후에 이를 제거할 수 있도록 해야 한다.
고민점 2: 최단 경로가 여러 가지인 경우를 어떻게 처리하지?
다만 최단 경로가 여러 가지인 경우를 고려하면 이 또한 그리 간단하지는 않다.
최단 경로가 여러 가지일 때에도 그 경로의 모든 도로를 제거해야 하는데, 단순히 직전 장소를 하나 기록한다면 이러한 효과를 얻을 수 없다.
이를 위해서는 다음 장소를 이미 방문했더라도 다시 방문하여 거리를 비교해야 한다.
다익스트라 알고리즘에서는 현재 노드가 이미 방문한 노드라면 이미 최단 경로가 지나간 것이므로 방문하지 않지만, 이 문제에서는 동일한 길이를 가진 또다른 최단 경로를 얻을 수 있어야 하기 때문에 다시 방문하여 거리를 비교한다.
다시 방문하였을 때의 거리가 기존 최단 경로의 거리와 같다면, 이때에도 직전 방문 장소를 기록하여 추후에 해당 경로를 따라가 제거할 수 있도록 해야 한다.
고민점 3: 그래서 이걸 어떻게 구현하지?
앞서 다익스트라를 두 번 사용한다는 아이디어와 이를 위한 첫번째 다익스트라의 역할을 설명했지만, 이를 어떤 자료구조로 구현할 수 있을 지를 고민해야 한다.
먼저 그래프는 HashMap의 배열을 이용하여 구현할 수 있다.
가중치가 없는 그래프라면 ArrayList의 배열로 다음 노드를 기록하여 인접 리스트의 형태로 나타낼 수 있지만, 이 경우에는 가중치가 존재하기 때문에 이를 사용할 수 없다.
HashMap을 사용해 key로는 다음 노드의 번호, value로는 그 때의 가중치를 기록하면 가중치 그래프를 충분히 표현할 수 있다.
첫번째 다익스트라에서 최단 경로로 직전에 방문한 장소는 ArrayList의 배열로 나타내면 된다.
이때는 단순히 해당 노드에 가장 짧은 거리로 도달했던 직전 장소들을 기록하면 되기 때문에 ArrayList의 배열로도 충분하다.
같은 거리로 도달할 수 있다면 그 때의 노드를 하나씩 추가하면 된다.
첫번째 다익스트라를 수행한 뒤 최단 경로를 제거할 때에는 재귀(recursive)를 사용하면 된다.
도착점에 최단 경로로 도달할 수 있는 직전 장소의 ArrayList를 훑으며 그 때의 도로를 제거하고, 이를 재귀적으로 따라가면서 도로들을 모두 제거하면 된다.
다만 그 과정에서 이미 방문했던 곳을 다른 경로에서 다시 방문할 수도 있기 때문에 이 때에도 방문 여부를 기록할 필요가 있다.
풀이
기본적인 아이디어는 다음과 같다.
- 각 테스트 케이스에 대해 다익스트라 알고리즘을 두 번 수행한다.
- 첫번째 다익스트라에서는 해당 장소에 최단 거리로 도달할 수 있는 직전 장소를 모두 기록한다.
- 첫번째 다익스트라가 끝난 후 해당 경로를 따라가며 도로를 모두 제거한다.
- 두번째 다익스트라는 남은 도로를 이용하여 진행한다. 이때의 값이 거의 최단 경로의 거리가 된다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main{
static HashMap<Integer, Integer>[] graph;
static boolean[] isErased;
public static void eraseShortest(ArrayList<Integer>[] lastVisit, int nextNode) {
if (lastVisit[nextNode].isEmpty()) return;
isErased[nextNode] = true;
for (int lastNode: lastVisit[nextNode]) {
graph[lastNode].remove(nextNode);
if (isErased[lastNode]) continue;
eraseShortest(lastVisit, lastNode);
}
}
static int INF = 2000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 테스트 케이스
while (true) {
StringTokenizer st1 = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st1.nextToken()); // 장소의 수
int M = Integer.parseInt(st1.nextToken()); // 도로의 수
// 입력이 "0 0" 이라면 종료
if (N == 0 && M == 0) break;
StringTokenizer st2 = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st2.nextToken()); // 시작점
int D = Integer.parseInt(st2.nextToken()); // 도착점
// 필요한 자료 구조 선언 및 초기화
int[] distance = new int[N]; // 최단 거리 기록 배열
graph = new HashMap[N]; // 그래프 배열
ArrayList<Integer>[] lastVisit = new ArrayList[N]; // 최단 거리일 때, 직전의 장소 번호 기록 배열
// 거리의 오름차순인 우선순위 큐
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1], o2[1]);
}
});
for (int i = 0; i < N; i++) {
distance[i] = INF;
graph[i] = new HashMap<>();
lastVisit[i] = new ArrayList<>();
}
// 그래프 구성
for (int i = 0; i < M; i++) {
StringTokenizer stm = new StringTokenizer(br.readLine());
int U = Integer.parseInt(stm.nextToken());
int V = Integer.parseInt(stm.nextToken());
int P = Integer.parseInt(stm.nextToken());
graph[U].put(V, P);
}
// 첫번째 다익스트라: 지나는 정점을 모두 기록한다.
// 시작점을 큐에 추가
int[] start = new int[] {S, 0};
pq.add(start);
distance[S] = 0;
while (!pq.isEmpty()) {
int[] now = pq.poll(); // {노드 번호, 시작점과의 최단 거리}
// key: 노드 번호, value: now[0]에서부터의 거리
for (Map.Entry<Integer, Integer> next: graph[now[0]].entrySet()) {
// 만약 최소값과 같다면 탐색은 더 하지 않지만, 직전 노드에는 추가함(다양한 최단 거리라는 뜻)
if (now[1] + next.getValue() == distance[next.getKey()]) {
lastVisit[next.getKey()].add(now[0]);
}
// 만약 새로운 최소 경로를 찾았다면 직전 노드를 초기화하고 새로 추가, 그리고 더 탐색한다.
else if (now[1] + next.getValue() < distance[next.getKey()]) {
int[] updatedNext = new int[] {next.getKey(), now[1] + next.getValue()};
pq.add(updatedNext);
distance[next.getKey()] = now[1] + next.getValue();
lastVisit[next.getKey()].clear();
lastVisit[next.getKey()].add(now[0]);
}
}
}
// 최단 거리의 도로를 모두 지운다.
isErased = new boolean[N];
for (int i = 0; i < N; i++) {
isErased[i] = false;
}
eraseShortest(lastVisit, D);
// 두번째 다익스트라: 최단 경로를 찾는다.
boolean[] isVisited = new boolean[N]; // 방문 여부 판단 배열
// 자료 구조를 다시 초기화
for (int i = 0; i < N; i++) {
distance[i] = INF;
isVisited[i] = false;
}
pq.clear();
// 시작점을 큐에 추가
int[] newStart = new int[] {S, 0};
pq.add(newStart);
distance[S] = 0;
while (!pq.isEmpty()) {
int[] now = pq.poll(); // {노드 번호, 시작점과의 최단 거리}
if (now[0] == D) break; // 만약 도착점에 도달한다면 더 진행할 필요 없이 끝낸다.
if (isVisited[now[0]]) continue; // 방문했던 노드라면 다시 보지 않는다.
isVisited[now[0]] = true; // 현재의 값이 무조건 최소 거리이다.
for (Map.Entry<Integer, Integer> next: graph[now[0]].entrySet()) {
if (isVisited[next.getKey()]) continue; // 방문했던 노드라면 다시 보지 않는다.
// 현재 탐색이 기존 탐색보다 더 짧은 경우
// 큐에 추가, 최단 거리 갱신
if (now[1] + next.getValue() < distance[next.getKey()]) {
int[] updatedNext = new int[] {next.getKey(), now[1] + next.getValue()};
pq.add(updatedNext);
distance[next.getKey()] = now[1] + next.getValue();
}
}
}
// 정답에 값 추가
if (distance[D] == INF) sb.append(-1+"\n");
else sb.append(distance[D]+"\n");
}
// 정답 출력
System.out.println(sb);
}
}회고
틀렸던 이유 1
재귀를 이용해 방문했던 도로를 제거하는 과정에서, 이미 방문했던 장소를 다시 방문하지 않는 코드를 작성하지 않아 시간 초과가 발생했다.
틀렸던 이유 2
방문 장소를 다시 방문하지 않는 코드를 작성했다. 다만 순서 상 현재 사용한 도로는 제거하고 다음 재귀를 진행하지 않아야 하는데, 사용한 도로를 제거하지 않고 끝내버려서 거의 최단 경로를 잘못 구하게 되었다.
