본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

[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]));
				}
			}
		}
	}

}
반응형