백준 | 5719번. 거의 최단 경로 - 다익스트라 문풀

⬛ 백준 5719번. 거의 최단 경로 - 다익스트라 문풀

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

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을 출력한다.

---

💚 문제 접근 방식

 초반에는 dijkstra로 최단 경로를 갱신하는 과정에서 계속 더 작은 값에 대해 갱신할 것이기 때문에, 갱신하는 값들을 전부 List에 담은 뒤, 2번째로 작은 값을 출력하도록 풀었는데, 이 방식은 pQ를 사용해서 가중치 작은 값을 우선 터치하므로, 정답을 보장 못한다는 사실을 깨달았다. 
 두 번째로는 경로를 삭제하는 부분을 떠올리긴 했지만, List.remove로 간선을 삭제하면 되는 것 아닌가 하는 생각으로 이어지자, 정확히 내가 원하는 간선 삭제를 위해 어떤 로직을 짜야 할지 막막해서 풀이가 막혔다.

• 문제에서, 최단 경로가 아니라 ‘거의 최단 경로’를 찾으라고 되어 있다.
• 즉, 직접 그래프 그려보면서 풀어보면 가장 최단 경로를 잇는 경로 간선을 삭제 처리 해주고 다익스트라를 다시 돌아야 하는 문제이다.
• exRoute가 true의 값을 갖는 특정 간선을 무시할 목적으로 활용해야 하고, removeList에서 도착점 D로부터 백트래킹 하면서 제거할 간선들을 담아, exRoute를 세팅해야 한다.

---

💚 제출 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 5719번. 거의 최단 경로 - 다익스트라 문풀 
 * @author MYLG
 *
 */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int N, M, S, D;
	static int[] distance;
	static boolean[][] exRoute;
	static List<Integer>[] removeList;
	static ArrayList<ArrayList<Edge>> graph;
	
	//dijkstra
	static int dijkstra(int s, int e) {
		Arrays.fill(distance, Integer.MAX_VALUE);
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//시작점
		distance[s] = 0;
		pQ.offer(new Edge(s, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(cur.val > distance[cur.e]) continue;
			
			for(Edge nx : graph.get(cur.e)) {
				if(exRoute[cur.e][nx.e]) continue;
				
				if(distance[nx.e] > distance[cur.e] + nx.val) {
					distance[nx.e] = distance[cur.e] + nx.val;
					removeList[nx.e] = new ArrayList<>();
					removeList[nx.e].add(cur.e);
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}else if(distance[nx.e] == distance[cur.e] + nx.val) {
					removeList[nx.e].add(cur.e);
				}
			}
		}
		return distance[e];
	}
	
	static void backTrackingDelete(int s, int d) {
		if(s==d) return;
		for(int nxt : removeList[d]) {
			//d에 연결된 값 
			if(!exRoute[nxt][d]) {
				exRoute[nxt][d] = true;
				backTrackingDelete(s, nxt);
			}
		}
		
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		while(true) {
			N = kb.nextInt();
			M = kb.nextInt();
			if(N == 0 && M == 0 ) break;
			
			S = kb.nextInt();
			D = kb.nextInt();
			
			removeList = new ArrayList[N]; //직전 정점 담기 
			for(int i=0; i<N; i++) {
				removeList[i] = new ArrayList<>();
			}
			distance = new int[N];
			graph = new ArrayList<>();
			for(int i=0; i<=N; i++) {
				graph.add(new ArrayList<>());
			}
			
			//데이터 입력 
			for(int i=0; i<M; i++) {
				int a  =kb.nextInt();
				int b = kb.nextInt();
				//방향 그래프
				int val = kb.nextInt();
				graph.get(a).add(new Edge(b, val));
			}			
			exRoute = new boolean[N][N];
			//다익스트라 
			dijkstra(S, D);
			//백트래킹 - delete 
			backTrackingDelete(S, D);
			dijkstra(S, D);
			
			if(distance[D] == Integer.MAX_VALUE) {
				System.out.println("-1");
			}else System.out.println(distance[D]);
			
		}	
	}
}

---

💚회고

 이 문제는 스스로 푸는 데에 실패했기 때문에 우선은 이해한 풀이 방식을 정리했고, 다음 번에 비슷한 유형의 문제를 만난다면, 이 매커니즘을 잘 활용할 수 있기를 바란다.