백준 5719 (거의 최단경로) | 다익스트라 , BFS

문제

---

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

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

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

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

 

 

풀이

---

이 문제는 특이하게 다익스트라 알고리즘과 BFS(너비우선 탐색)을 두개다 사용해야하는 문제다.

List 로 문제를 풀려했는데 List 로 풀시에 최단거리에 해당하는 경로를 지울시에 방향성이 있는 그래프기 때문에 반대로 돌아가는 게 복잡해서 int의 이중배열을 사용하였다.

 

문제푸는 순서는

1. 다익스트라 알고리즘을 통해 최단거리를 구한다.
2. 너비우선 탐색을 통해 목적지 최단거리와 같은 값을 가지는 경로를 모두 지워준다.
3. 다익스트라 알고리즘을 통해 최단거리를 구한다.

이런 방식으로 하면 된다.

 

우선 다익스트라 알고리즘 코드다.

static int[] Dijkstra(int n, int[][] road, int start, int destination) {
		PriorityQueue<edge> pq = new PriorityQueue<edge>();
		int[] dist = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			if(i == start) {
				dist[i] = 0;
			}
			else {
				dist[i] = Integer.MAX_VALUE;
			}
			
			pq.add(new edge(i, dist[i]));
		}
	
		while(!pq.isEmpty()) {
			edge Edge = pq.poll();
			
			for(int i = 0 ; i < n ; i++) {
				
				if(road[Edge.v][i] == 0)
					continue;
				
				if(dist[Edge.v] != Integer.MAX_VALUE && (dist[i] > dist[Edge.v] + road[Edge.v][i])) {
					dist[i] = dist[Edge.v] + road[Edge.v][i];
					
					pq.add(new edge(i, dist[i]));
				}
			}
		}
		
		return dist;
	}

 

 

너비우선탐색 코드다.

static int[][] deleteNode(int n, int[] dist, int[][] road, int start, int destination){
		
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(destination);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
		
			for(int i = 0 ; i < n ; i++) {
				
				if(road[i][now] == 0)
					continue;
				
				if(dist[now] == dist[i] + road[i][now]) {
					
					road[i][now] = 0;
					queue.add(i);
				}
			}
		}
		
		return road;
	}

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	
	static class edge implements Comparable<edge>{
		
		int v, p;
		
		public edge(int v, int p) {
			this.v = v;
			this.p = p;
		}

		@Override
		public int compareTo(edge o1) {
			// TODO Auto-generated method stub
			
			return Integer.compare(this.p, o1.p);
		}
		
		
	}
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
		while(true) {
			String[] NM = bufferedReader.readLine().split("\\s");
			int n = Integer.parseInt(NM[0]);
			int m = Integer.parseInt(NM[1]);
			if(n == 0 && m == 0 ) { break; }
			
			int[][] road = new int[n][n];
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					road[i][j] = 0;
				}
			}
					
			String[] sd = bufferedReader.readLine().split("\\s");
			int start = Integer.parseInt(sd[0]);
			int destination = Integer.parseInt(sd[1]);
			
			for(int i = 0 ; i < m ; i++) {
				String[] uvp = bufferedReader.readLine().split("\\s");
				
				int u = Integer.parseInt(uvp[0]);
				int v = Integer.parseInt(uvp[1]);
				int p = Integer.parseInt(uvp[2]);
				
				road[u][v] = p;
			}
			int[] dist = Dijkstra(n, road, start, destination);
			road = deleteNode(n, dist, road, start ,destination);
			dist = Dijkstra(n, road, start, destination);
			
			int min = dist[destination];
			if(min == Integer.MAX_VALUE)
				min = -1;
			sb.append(min+ "\n");
		}
	    
		System.out.println(sb);
	}
	
	static int[] Dijkstra(int n, int[][] road, int start, int destination) {
		PriorityQueue<edge> pq = new PriorityQueue<edge>();
		int[] dist = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			if(i == start) {
				dist[i] = 0;
			}
			else {
				dist[i] = Integer.MAX_VALUE;
			}
			
			pq.add(new edge(i, dist[i]));
		}
	
		while(!pq.isEmpty()) {
			edge Edge = pq.poll();
			
			for(int i = 0 ; i < n ; i++) {
				
				if(road[Edge.v][i] == 0)
					continue;
				
				if(dist[Edge.v] != Integer.MAX_VALUE && (dist[i] > dist[Edge.v] + road[Edge.v][i])) {
					dist[i] = dist[Edge.v] + road[Edge.v][i];
					
					pq.add(new edge(i, dist[i]));
				}
			}
		}
		
		return dist;
	}
	
	static int[][] deleteNode(int n, int[] dist, int[][] road, int start, int destination){
		
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(destination);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
		
			for(int i = 0 ; i < n ; i++) {
				
				if(road[i][now] == 0)
					continue;
				
				if(dist[now] == dist[i] + road[i][now]) {
					
					road[i][now] = 0;
					queue.add(i);
				}
			}
		}
		
		return road;
	}
	
}