5719번: 거의 최단 경로
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있
www.acmicpc.net
문제
요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.
상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.
거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.
예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.
문제 접근
시간 제한은 1초
메모리 제한은 256MB 입니다.
먼저 문제를 봤을 때 저희가 해야 할 일은 다음과 같습니다.
- 최단 경로를 구한다
- 최단 경로(복수 가능)를 없앤다.
- 다시 최단 경로를 구해라
2 ≤ 장소의 수 N ≤ 500
1 ≤ 도로의 수 M ≤ 10000
최악의 경우 모든 장소를 들리면서 도로를 확인한다고 하면 O(N*M)으로 500 * 10000 입니다.
음수의 가중치가 없는 최단 경로를 구하는 문제이므로 바로 다익스트라로 접근하면 됩니다.
다익스트라는 힙을 이용하여 최단 경로 비용을 찾으며 O(VlogE)입니다.
해결 방법
- 다익스트라 알고리즘을 이용하여 각 정점의 최단 경로 비용을 구합니다.
- 도착 지점에서 각 정점의 최단 경로 비용이 맞는 정점을 지워서 최단 경로를 지웁니다.
- 지워진 상태에서 다익스트라 알고리즘을 이용해서 다시 최단 경로 비용을 구하여 출력합니다.
어려웠던 점
저는 2번 최단 경로를 지우는 부분에서 문제가 생겼습니다.
처음에 간선과 가중치를 Route라는 클래스를 만들어 List<Route>[] adj으로 만들어 저장하였습니다.
후에 dfs를 이용해서 D(기존 목적지)에서 S(기존 출발점)로 도착함과 동시에 비용이 최소 였을 때 2차원 배열에 해당 간선들의 좌표를 저장했습니다.
후에 2차원 배열을 이용하여 최단 경로가 되는 정점을 지우는 방법을 선택했습니다.
물론 기존 간선들을 역으로 뒤집어서 만들어야 하고 다시 2차원 배열에 간선을 저장해서 후에 처리해주는게 번거로웠습니다.
실제 결과는..
dfs를 돌리면서 계속 간선을 저장하고 마지막 처리할 때 좌표에 넣어주는 방식이였습니다.
하지만 만개 이상의 데이터가 쌓일 수 있어 메모리 초과하고 말았습니다.
고친 점
처음에 입력 값으로 받은 간선과 가중치를 2차원 배열로 받았습니다.
장소의 수가 최대 500으로
250,000 크기의 배열이 생성되지만 실제로 접근하는데 O(1)밖에 걸리지 않고
dfs가 아닌 bfs로 최단 경로 간선을 구할 수 있어 메모리 초과도 피할 수 있었습니다.
내 코드
구현한 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M, S, D;
static int[][] adj;
static int[] value;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 0 && M == 0) {
break;
}
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
adj = new int[N][N];
value = new int[N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
adj[a][b] = c;
}
dijkstra();
deleteShortestRoute();
dijkstra();
if (value[D] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(value[D]);
}
}
}
// 최단 경로 삭제
static void deleteShortestRoute() {
Queue<Integer> queue = new LinkedList<>();
// 역으로 시작할 D를 넣는다.
queue.add(D);
while (!queue.isEmpty()) {
int current = queue.poll();
for (int i = 0; i < N; i++) {
//
if (adj[i][current] != 0 && value[current] == value[i] + adj[i][current]) {
adj[i][current] = 0;
queue.add(i);
}
}
}
}
static void dijkstra() {
Arrays.fill(value, Integer.MAX_VALUE);
value[S] = 0;
PriorityQueue<Route> queue = new PriorityQueue<>(Comparator.comparingInt(Route::getC));
// 시작점 S
queue.add(new Route(0, S, 0));
while (!queue.isEmpty()) {
Route poll = queue.poll();
// 정점 b까지의 가중치를 설정한다.
for (int i = 0; i < N; i++) {
// 현재 정점 b에 대해서 연결된 정점을 찾는다.
if (adj[poll.b][i] != 0) {
// 정점 b와 연결될 정점 i 이 있다면
if (value[i] > poll.c + adj[poll.b][i]) {
// 발견된 정점 i까지 기존 가중치가
// 정점 b까지의 가중치 + 정점 b에서 i까지의 가중치를 더했을 떄 보다 클 때
// 큐에 i와 연결된 정점들과 그에 대한 가중치를 최신화하여 넣는다.
value[i] = poll.c + adj[poll.b][i];
queue.add(new Route(poll.b, i, poll.c + adj[poll.b][i]));
}
}
}
}
}
}
class Route {
int a, b, c;
public Route(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
public int getC() {
return c;
}
}
댓글