[BOJ 백준] 거의 최단 경로(5719) Java

링크 : https://www.acmicpc.net/problem/5719

 

문제 설명 : 

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

 

입력 : 

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다. 

입력의 마지막 줄에는 0이 두 개 주어진다.

 

출력 : 

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

 

예제 입력 : 

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

 

예제 출력 : 

5

-1

6

 

접근법 : 

1) 어떻게 풀 것인가?

최단경로 문제이고 음수 간선이 없으며, 출발지-도착지가 명확하다.

여기까지만 보면 무난한 다익스트라 문제인데, 제약조건이 있다.

 

"최단경로가 아닌 도로들만 이용해야한다."

 

이 제약 조건을 해결하려면 아래와 같이 진행하면 된다.

① 최단경로'들'을 기록한다

② 최단경로'들'을 지운다

③ 다익스트라로 가능한 경로 중 가장 빠른 길을 찾는다

 

위 내용을 구체화하면 

① 다익스트라를 진행하면서, 최단경로 동일한 값들을 기록한다

   - ( dist[next.id] == now.cost + next.cost ) 일때 경로를 기록

 

② DFS를 활용해서 도착지 D에서부터 출발지 S로 경로를 백트래킹해,

   해당 최단경로'들'을 지운다

 

③ 다익스트라로 가능한 경로 중 가장 빠른 길을 찾는다

 

으로 진행하면된다.

 

자세한 내용은 아래 코드 참고.

 

2) 시간복잡도

PQ를 활용한 다익스트라의 경우 시간 복잡도 O(ElogV).

테스트 케이스가 몇개인지 불확실하나 통과하는데는 무리 없음.

(Java 기준 -  596ms)

 

3) 공간복잡도

도로의 수가 10,000개로 작아 고려하지 않음

 

4) 풀면서 놓쳤던점

dist[ i ] 배열을 전역으로 1번만 초기화해서 답이 틀림

→ 다익스트라를 2번 돌리기 때문에 다익스트라 함수 안으로 이동.

 

5) 이 문제를 통해 얻어갈 것

다익스트라 기본 코드, 1개가 아닌 N개 목적지를 필요로할때 활용법.

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 5719 거의 최단 경로
public class Main {

	static class Edge implements Comparable<Edge> {
		int targetId, cost;

		public Edge(int targetId, int cost) {
			this.targetId = targetId;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	static int N, M, S, D; // N - 정점 수, M - 간선 수, S - 출발점, D - 도착점
	static int[] dist;
	static ArrayList[] adjList;
	static int ans; // 출력할 답

	// 거의 최단경로 전용 변수
	static boolean[][] isShortest;
	static ArrayList[] parent;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringBuilder sb = new StringBuilder(); // 정답 출력용

		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		for (; N != 0 && M != 0;) {

			// ★★★★ 정점은 0 ~ N-1로 구성
			// 1. 각종 배열 초기화 
			isShortest = new boolean[N][N];
			parent = new ArrayList[N];
			adjList = new ArrayList[N];
			for (int i = 0; i < N; i++) {
				parent[i] = new ArrayList<Integer>();
				adjList[i] = new ArrayList<Edge>();
			}

			// 2. 입력
			st = new StringTokenizer(br.readLine());
			S = Integer.parseInt(st.nextToken());
			D = Integer.parseInt(st.nextToken());

			// 3. 방향간선 인접리스트 입력
			int u, v, p;
			for (int i = 1; i <= M; i++) {
				st = new StringTokenizer(br.readLine());

				u = Integer.parseInt(st.nextToken());
				v = Integer.parseInt(st.nextToken());
				p = Integer.parseInt(st.nextToken());

				// 단방향 간선
				adjList[u].add(new Edge(v, p));
			}

			// 4. 출발지부터 다익스트라 진행
			dijkstra(S, D);
			backTracking(S, D);
			dijkstra(S, D);

			// 5. 정답 출력
			if (dist[D] == Integer.MAX_VALUE) {
				sb.append("-1\n");
			} else {
				sb.append(dist[D] + "\n");
			}

			// 다음 N, M 입력 - 0,0 입력시 종료
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
		}

		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}

	// dest에서 start 방향으로 tracking
	static void backTracking(int start, int now) {
		
		if (start == now) return;	// 도착했으니 끝
		
		int len = parent[now].size();
		for (int i = 0; i < len;i++) {
			
			int next = (int) parent[now].get(i);
			
			if (!isShortest[next][now]) {
				isShortest[next][now] = true;		// 최단경로라고 체크해주고
				backTracking(start, next);			// dfs 추가 진행
			}
			
		}
	}

	static void dijkstra(int start, int dest) {
		// 다익스트라 2번 돌리므로 다익스트라 함수 내에서 inf로 초기화
		dist = new int[N];
		for (int i = 0; i<N; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		
		// 1. 출발지 비용은 0으로 하고 출발지를 PQ에 넣고 시작
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		dist[start] = 0;
		pq.add(new Edge(start, 0));

		while (!pq.isEmpty()) {
			Edge now = pq.poll();

			// * 특정 목적지에 도착하는 문제였다면, 도착지 도착후 break

			// 2. 더 큰 가중치로 도착한 경우 패스
			if (now.cost > dist[ now.targetId ])
				continue;

			// 3. 현재 위치에 연결된 간선 탐색
			int len = adjList[ now.targetId ].size();
			for (int i = 0; i < len; i++) {
				Edge next = (Edge) adjList[ now.targetId ].get(i);

				// 최단경로 간선이면 continue - 2번째 다익스트라를 위한 로직
				if (isShortest[ now.targetId ][ next.targetId ])
					continue;

				// ★★★★ 최단경로 모두를 넣어줘야하므로, 다른 최단경로일 경우 백트래킹 대상(parent)에 추가
				if ( dist[next.targetId ] == now.cost + next.cost) {
					parent[ next.targetId ].add(now.targetId );
				}

				// 4. cost가 더 작을때만 갱신하고 PQ에 넣기
				else if (dist[next.targetId] > now.cost + next.cost) {
					dist[next.targetId] = now.cost + next.cost;

					// 새로운 parent가 생겼으므로 비어주고 넣기
					parent[next.targetId].clear();
					parent[next.targetId].add(now.targetId);
					pq.add(new Edge(next.targetId, dist[next.targetId]));
				}
			}
		}
	}

}