[boj-1504]특정한 최단경로

dijkstra 알고리즘을 사용하여 최단경로의 길이를 찾는 문제지만,

1. 특정 정점 두개(e1, e2)는 반드시 경유해야 함
2. 지나갔던 정점이나 간선을 다시 지나갈 수 있음

이 두가지 조건이 추가된 문제였다. 시작점이 1이고 n이 도착점일 때, 이 두가지 조건을 만족하는 최단거리를 구해야 하는 것이 이 문제이다.

처음에는 단순하게 문제를 3가지 작은 문제로 나누었다. 

• 시작점 1부터 e1까지 dijkstra를 수행하여 e1까지의 최단경로를 찾음
• e1부터 e2까지 최단경로를 찾음. 이 때 전에 수행한 최단경로의 정보는 사용하지 않는다. 지나갔던 간선이나 정점을 다시 방문할 수 있으니까..
• 마찬가지로 e2부터 도착점 n까지 dijkstra 수행..

이렇게 했더니 당연 꽝... 빠뜨린 조건이 있나 이짓 저짓하면서 반례를 찾아보았지만 별 소득이 없었고, 결국 질문 게시판의 내용을 확인했더니, 시작점 1에서 출발하여 먼저 e1을 경유하는 경우와 e2를 먼저 경유하는 경우 값이 달라질 수 있다는 것을 알게 되었다. 이를 깨닫고 다시 생각하여 각각의 경우에 갖는 최단거리를 비교하여 최소값을 반환하도록 만들었다. 어찌저찌 만들었는데 100%에서 틀렸다고 한다.. 미칠 노릇이였다. 다시 검색하며 찾은 문제점은

1. 최단 경로의 값인 dist가 int형이면 overflow가 일어날 수 있다. 따라서 long 타입으로 바꿔야 한다.
2. dijkstra에서 최단 거리를 업데이트하는 과정인 dist[v] = dist[u]+w[u,v] 연산 중 오버플로우가 일어날 수 있다는 점이였다. 따라서 d의 초기값인 INF 값을 적당한 값으로 바꿔야 했다.

이 문제를 해결하니 드디어 해결이 되었다. 

그리고 두 가지의 최단경로를 dijkstra로 구할 때, 어차피 single-source 방식이기 때문에 출발점을 기준으로 0, e1, e2인 경우 즉 3번만 호출하면 된다.

인접행렬 방식으로 만들어서 그런지 몰라도 속도면에서는 다소 떨어진다. 인접 정점들을 확인하는데 O(n)의 시간복잡도가 요구되기 때문이다.

package graph.shortestPath; import java.io.*; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class ShortestPath2 { public final static long INF = 300000000; private static long[][] d = new long[3][801]; private static int n; private static int e; private static int[][] map = new int[801][801]; static { for (int i = 0; i < 3; i++) { Arrays.fill(d[i], INF); } } public static void main(String[] args) throws IOException { //BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("shortestPath2.txt"))); StringTokenizer st = new StringTokenizer(br.readLine(), " "); n = Integer.parseInt(st.nextToken()); e = Integer.parseInt(st.nextToken()); for (int i = 0; i < e; i++) { st = new StringTokenizer(br.readLine(), " "); int prev = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); map[prev][to] = w; map[to][prev] = w; } st = new StringTokenizer(br.readLine(), " "); int e1 = Integer.parseInt(st.nextToken()); int e2 = Integer.parseInt(st.nextToken()); dijkstra(1, 0); dijkstra(e1, 1); dijkstra(e2, 2); long dist1 = d[0][e1] + d[1][e2] + d[2][n]; long dist2 = d[0][e2] + d[2][e1] + d[1][n]; long result = Math.min(dist1, dist2); if (result >= INF) { System.out.println(-1); } else { System.out.println(result); } } public static void dijkstra(int start, int idx) { d[idx][start] = 0; PriorityQueue<Integer> queue = new PriorityQueue<>(); queue.add(start); while (!queue.isEmpty()) { int v = queue.remove(); for (int i = 1; i <= n; i++) { if (map[v][i] != 0 && d[idx][i] > d[idx][v] + map[v][i]) { d[idx][i] = d[idx][v] + map[v][i]; queue.add(i); } } } } }