[BOJ-5719] 거의 최단 경로(Java)

백준 5719 거의 최단 경로

 

5719번: 거의 최단 경로

 

문제 설명

 

 - 상근이는 자기만 사용 가능한 네비게이션을 만들려 한다.

 

 - 이 네비게이션은 거의 최단 경로만 찾아준다.

 

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

 

 - 최단 경로나 거의 최단 경로는 여러 개 존재할 수 있다.

 

 - 거의 최단 경로가 없는 경우도 존재할 수 있다.

 

 - 거의 최단 경로를 길이를 출력하라. 거의 최단 경로가 없는 경우 -1을 리턴하라.

 

---

 

입력 값

 

 - 여러 개의 테스트 케이스로 이루어져 있다.

 

 - 각 테스트 케이스의 첫째 줄에는 장소의 수 N, 도로의 수 M 이 주어진다.( 2 <= N <= 500, 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이 두 개 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 거의 최단 경로라고 함은 최단 경로에 포함된 도로가 아닌 도로들 중 최단 경로를 말한다.

 

 - 즉, 최단 경로에 포함된 도로를 찾아 제거하고, 남은 도로 중 최단 경로를 찾으면 거의 최단 경로를 찾을 수 있다.

 

 - 각 도로의 방향과 가중치가 존재한다. 또한, 가중치는 양의 정수이다.

 

 - 그렇기 때문에 다익스트라를 이용하면 최단 경로를 찾을 수 있다.

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

 - 다익스트라를 이용하여 최단 경로에 어떤 도로가 포함되는지 찾는 방법은 다익스트라를 돌면서 현재 노드의 직전 노드를 저장하면 된다.

 

 - 현재 방문한 노드가 i이고, 노드 j로 가는 경우 nodes[i].add(j) 형태로 도착한 노드들을 저장하면 된다.

 

 - 주의할 점은, 가중치가 같은 경우에 추가를 해주고 가중치가 작아지는 경우 노드를 초기화한 후 추가해줘야 한다는 점이다.

 

 - 첫 다익스트라를 통해 최단 경로에 해당하는 도로들을 찾는다.

 

 - 그 이후에 해당 도로들을 지워준다.

 

 - 다시 다익스트라를 통해 최단 경로를 찾으면, 해당 최단 경로가 거의 최단 경로가 된다.

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// https://www.acmicpc.net/problem/5719
// 거의 최단 경로
public class Main {
    // 경로 가중치 저장
    public static int boards[][] = new int[501][501];
    // weights[i] => i 까지 가는 최소 가중치
    public static int weights[] = new int[501];
    // nodes[i] => i 까지 최소 가중치로 왔을 때 직전 노드들
    public static Set<Integer> nodes[] = new Set[501];
    // 삭제 시 해당 노드 이미 지웠는지 확인
    public static boolean check[] = new boolean[501];

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(st.nextToken());

        while(N != 0 && M != 0){

            st = new StringTokenizer(bf.readLine());

            int S = Integer.parseInt(st.nextToken());

            int D = Integer.parseInt(st.nextToken());
            
            init();

            for(int i=0;i<M;i++){
                st = new StringTokenizer(bf.readLine());

                int U = Integer.parseInt(st.nextToken());

                int V = Integer.parseInt(st.nextToken());

                int P = Integer.parseInt(st.nextToken());

                boards[U][V] = P;
            }
            // 다익스트라 돌려서 최단 경로 찾기
            Dijkstra(S);
            // 최단 경로 지우기
            deletePath(D);
            // 가중치 저장한 부분 지우기
            weightsInit();
            // 거의 최단 경로 찾기
            Dijkstra(S);

            System.out.println(weights[D] == Integer.MAX_VALUE ? -1 : weights[D]);

            st = new StringTokenizer(bf.readLine());

            N = Integer.parseInt(st.nextToken());

            M = Integer.parseInt(st.nextToken());
        }

    }

    public static void deletePath(int d){
        if(check[d]){
            return;
        }
        
        check[d] = true;
        for(int i : nodes[d]){
            boards[i][d]=Integer.MAX_VALUE;
            deletePath(i);
        }
    }

    public static void Dijkstra(int S){

        boolean visited[] = new boolean[501];

        weights[S] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(S,0));

        while(!pq.isEmpty()){

            Node nowNode = pq.poll();

            if(visited[nowNode.index]){
                continue;
            }
            visited[nowNode.index] = true;

            for(int i=0;i<501;i++){
                if(visited[i] || boards[nowNode.index][i] == Integer.MAX_VALUE){
                    continue;
                }
                if(nowNode.value + boards[nowNode.index][i] > weights[i]) {
                    continue;
                }
                // i번째 노드까지 최단 경로가 새로 갱신되는 경우 기존 직전 노드 초기화
                if(nowNode.value + boards[nowNode.index][i] < weights[i]){
                    nodes[i].clear();
                }
                // i번째 노드까지 최단 경로로 왔을 때 직전 노드 저장
                nodes[i].add(nowNode.index);

                weights[i] = nowNode.value + boards[nowNode.index][i];
                pq.add(new Node(i,weights[i]));
            }

        }
    }

    static class Node implements Comparable<Node>{
        int index;
        int value;

        public Node(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }

    }

    public static void init(){
        for(int i=0;i<501;i++){
            for(int j=0;j<501;j++){
                boards[i][j]=Integer.MAX_VALUE;
            }
            check[i]=false;
        }

        weightsInit();

    }

    public static void weightsInit(){
        for(int i=0;i<501;i++){
            nodes[i] = new HashSet<>();
            weights[i] = Integer.MAX_VALUE;
        }
    }
}