백준 5719번: 거의 최단 경로 (Java)

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

 

---

 

풀이

시작점에서부터 다익스트라를 돌려 경로 추적을 하면서(코드의 prevs[cur]: cur까지 최단으로 오는 경로들의 직전 장소의 집합') 최단 경로들을 찾아준다.

도착점에서부터 역추적하여, 최단 경로로 갈 때 들르는 점들을 체크한다.

이후 시작점에서부터 다시 다익스트라를 돌리되, 만약 '최단 경로에서 방문한 점이고 prevs[방문했던 점의 위치] 집합이 현재 노드의 위치를 가지고 있다'면 이는 최단 경로에 해당하는 도로이므로, 방문하지 않는다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        while (N != 0) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int D = Integer.parseInt(st.nextToken());
            List<List<Edge>> graph = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                graph.add(new ArrayList<Edge>());
            }
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int U = Integer.parseInt(st.nextToken());
                int V = Integer.parseInt(st.nextToken());
                int P = Integer.parseInt(st.nextToken());
                graph.get(U).add(new Edge(V, P));
            }
            
            HashSet<Integer>[] prevs;
            prevs = (HashSet<Integer>[]) new HashSet[N+1];
            for (int i = 0; i <= N; i++) {
                prevs[i] = new HashSet<Integer>();
            }
            
            // 최단 경로들을 찾는 다익스트라
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            int[] d = new int[N+1];
            Arrays.fill(d, Integer.MAX_VALUE);
            pq.offer(new Edge(S, 0));
            d[S] = 0;
            while (!pq.isEmpty()) {
                Edge cur = pq.poll();
                if (d[cur.loc] < cur.dist) continue;
                for (Edge nxt: graph.get(cur.loc)) {
                    if (d[nxt.loc] < cur.dist + nxt.dist) continue;
                    else if (d[nxt.loc] == cur.dist + nxt.dist) {
                        prevs[nxt.loc].add(cur.loc);
                    } else {
                        prevs[nxt.loc].clear();
                        prevs[nxt.loc].add(cur.loc);
                        d[nxt.loc] = cur.dist + nxt.dist;
                        pq.offer(new Edge(nxt.loc, cur.dist+nxt.dist));
                    }
                }
            }
            
            // 최단 경로에서 방문하는 점들을 기록
            boolean[] visited = new boolean[N+1];
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(D);
            visited[D] = true;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int prev: prevs[cur]) {
                    if (visited[prev]) continue;
                    visited[prev] = true;
                    queue.offer(prev);
                }
            }
            
            // 최단 경로에서 지나가는 도로를 제외하여 다익스트라
            Arrays.fill(d, Integer.MAX_VALUE);
            pq.offer(new Edge(S, 0));
            d[S] = 0;
            while (!pq.isEmpty()) {
                Edge cur = pq.poll();
                if (d[cur.loc] < cur.dist) continue;
                for (Edge nxt: graph.get(cur.loc)) {
                    if (visited[nxt.loc] && prevs[nxt.loc].contains(cur.loc)) continue;
                    if (d[nxt.loc] <= cur.dist + nxt.dist) continue;
                    d[nxt.loc] = cur.dist + nxt.dist;
                    pq.offer(new Edge(nxt.loc, d[nxt.loc]));
                }
            }
            System.out.println((d[D] == Integer.MAX_VALUE)? -1: d[D]);
            
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
        }
    }
    
    static class Edge implements Comparable<Edge> {
        int loc;
        int dist;
 
        public Edge(int loc, int dist) {
            this.loc = loc;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}