[백준] 5719 거의 최단 경로 - JAVA

 

5719번: 거의 최단 경로 (acmicpc.net)

5719번: 거의 최단 경로

 

풀이

알고리즘 파악

다익스트라 + DFS

 

출발점 S에서 D까지 가는 최단경로를 구하는 문제이다. 단, 단순한 최단경로가 아닌, (복수의) 최단경로를 제외한 나머지 경로에서의 최단거리를 구하는 것이다. 

 

구현

 

총 두번의 다익스트라와 dfs를 통한 경로 탐색을 진행한다. 

 

1. 다익스트라를 돌려 최단길이를 모두 구한다.

이 과정에서 이차원 boolean 배열인 route에 경로를 저장한다. 여기서 주의할점은 최단경로를 전부 구해서 저장 해야 한다는 것이다. 일반적인 다익스트라는 최단거리 만을 구하지만, 지금은 경로도 전부 저장해야 한다는 것이다. 

이를 route[목적지][출발지] 로 구현하였다. 길이가 같으면 기존에 출발지를 추가하고, 더 짧은 길이로 갱신이 되면 출발지를 초기화 하도록 하였다. 

 

2. DFS를 통해 최단길이의 경로들을 모두 구한 후 제거한다.

dfs를 사용해 목적지로부터 역추적을 하고, 이 과정에서 구해진 경로들을 전부 제거한다. (closed 배열에 저장)

보기에는 굉장히 간단해 보인다. 하지만 이 문제의 실질적인 복병이다.

실제로 메모리 및 시간 초과를 겪었을때 전혀 여기서는 문제점을 파악하지 못했다. 결국 질문검색 게사판에서 힌트를 얻은뒤 문제를 파악했다. (나 말고도 상당히 많은 사람들이 여기서 막혔다...) 

 

문제는 여기서 무한 Loop이 발생할 수 있다는 것이다.  

이는 예시를 통해 살펴보는 것이 제일 직관적이다. 

ex)

     s - 1 - 2 - 3 - d

    와

     s - 3 - 1 - d

    의 길이가 서로 같을 수 있다.  

    즉 d - 3 - 2 - 1 - 3 - 2 - 1 - 3 - 2 - 1  - ..... 이런식으로 무한 loop 에 빠지는 것이다! 깊게 생각해 보지 않으면 충분히 빠질 만한 포인트 였다!

 

3. 다익스트라를 한번 더 돌려 최단경로가 제외된 나머지 경로에서의 최단거리를 구한다(거의 최단 경로).

이 마지막 과정에서는 굳이 route를 구할 필요가 없다. 그래서 order 매개변수를 통해 route 계산을 없애 버렸다. 

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
	static int n,m,s,d;
	static ArrayList<Edge>[] graph;
	static boolean[][] route; //경로
	static boolean[][] closed; //제거된 경로
	static PriorityQueue<Edge> pq;
	static int[] costs;
	static final int INF = 987654321;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw  =new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		while(true)
		{
		 StringTokenizer st =new StringTokenizer(br.readLine());	
		 n = Integer.parseInt(st.nextToken());
		 m = Integer.parseInt(st.nextToken());
		 if(n==0 && m==0) break;
		 
		 st =new StringTokenizer(br.readLine());	
		 s = Integer.parseInt(st.nextToken());
		 d = Integer.parseInt(st.nextToken());
		 graph = new ArrayList[n]; 
		 
		 for(int j=0; j<n; j++) graph[j] = new ArrayList<>(); //초기화
		 
		 for(int j=0; j<m; j++)
		 {
			 st = new StringTokenizer(br.readLine());
			 int a = Integer.parseInt(st.nextToken());
			 int b = Integer.parseInt(st.nextToken());
			 int c = Integer.parseInt(st.nextToken());
			 graph[a].add(new Edge(b,c));
		 }
		 
		 Dijkstra(1); 	
		 CloseRoute(d,new boolean[n][n]);
		 Dijkstra(2);
		 
		 if(costs[d]!=INF)sb.append(costs[d]+"\n");
		 else sb.append(-1+"\n");
		}
		
		bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
	}
    
	static void Dijkstra(int order)
	{
		if(order==1) {route = new boolean[n][n]; closed = new boolean[n][n];} //첫번째 다익스트라 - 루트 생성 필요
		costs = new int[n];
		for(int j=0; j<n; j++) costs[j] = INF;  //초기화 
		
		costs[s] =0; //시작
		pq = new PriorityQueue<>();
        pq.offer(new Edge(s,0));
		
        while(!pq.isEmpty())
        {
        	Edge edge = pq.poll();
        	if(edge.cost > costs[edge.idx]) continue;
        	
        	ArrayList<Edge> cur_list = graph[edge.idx];
        	
        	int cur_cost = edge.cost;
        	for(Edge other:cur_list)
        	{
        		if(!closed[edge.idx][other.idx] && (costs[other.idx] > cur_cost + other.cost)) //경로가 더 짧다 +제거되지 않은 경로
        		{
        			if(order==1) //첫번째 다익스트라
        			{
        				if(costs[other.idx] > cur_cost + other.cost) {route[other.idx] = new boolean[n];} // 더 짧음 
        				route[other.idx][edge.idx]= true;
        			}
        			costs[other.idx] = cur_cost + other.cost;
        			pq.offer(new Edge(other.idx,costs[other.idx]));
        		}
        		else if(order==1&&!closed[edge.idx][other.idx] && (costs[other.idx] == cur_cost + other.cost)) //똑같다 - 경로 저장
        		{
        			route[other.idx][edge.idx]= true;
        		}
        	}
        }
	}
    
    static void CloseRoute(int idx,boolean[][] visit) //경로 제거
	{
		for(int i=0; i<n; i++)
		{
			if(route[idx][i] && !visit[idx][i] ) //나에게 도착
			{
				closed[i][idx] = true;
				visit[idx][i] = true;
				setShortRoute(i,visit);
			}
		}
		
	}
	
	static class Edge implements Comparable<Edge>
	{
		int idx;
		int cost;
		
		Edge(int idx,int cost)
		{
			this.idx = idx;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge other)
		{
			return this.cost -other.cost;
		}
	}
}