BOJ5719 거의 최단 경로 java

문제

요즘 많은 자동차에서는 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을 출력한다.

풀이 방법

1. 다익스트라 최단 경로에 포함되는 모든 간선을 추적
2. 초기 최단 경로에 포함된 간선을 제외한 뒤에, 다시 최단 경로를 탐색

🤔 최단 경로를 구성하는 간선들은 어떻게 찾지?

 

BFS를 사용하여 역추적을 하여 제거해준다.

25% 메모리초과

25%에서 메모리초과가 났다.

import java.util.*;
import java.io.*;

public class Main {
    static int N,M,D;
    static List<Road>[] map;
    static List<Road>[] reverseMap;
    static int[] distances;
    static boolean[][] dropped;

    static class Road implements Comparable<Road> {
        private int node;
        private int edge;

        Road(int node, int edge) {
            this.node = node;
            this.edge = edge;
        }

        @Override
        public int compareTo(Road o) {
            return o.edge - this.edge;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.valueOf(st.nextToken());
            M = Integer.valueOf(st.nextToken());
            if(N == 0 && M == 0) break;
            dropped = new boolean[N][N];
            distances = new int[N];

            map = new List[N];
            reverseMap = new List[N];

            for(int i = 0;i<N;i++) {
                map[i] = new ArrayList<>();
                reverseMap[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            int S = Integer.valueOf(st.nextToken());
            D = Integer.valueOf(st.nextToken());

            for(int i = 0;i<M;i++) {
                st = new StringTokenizer(br.readLine());
                int U = Integer.valueOf(st.nextToken());
                int V = Integer.valueOf(st.nextToken());
                int P = Integer.valueOf(st.nextToken());
                map[U].add(new Road(V,P));
                reverseMap[V].add(new Road(U,P));
            }

            dijkstra(S);
            bfs(S);
            dijkstra(S);

            if(distances[D] != Integer.MAX_VALUE) {
                sb.append(distances[D]);
            } else {
                sb.append(-1);
            }
            sb.append("\\n");
        }

        System.out.println(sb.toString().trim());

    }

    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(D);
        while(!q.isEmpty()) {
            int now = q.poll();
            if(now == start) continue;
            List<Road> roads = reverseMap[now];
            for(Road road : roads) {
                int prev = road.node;
                int edge = road.edge;
                if(dropped[prev][now])continue;
                if(distances[now] == distances[prev] + edge) {
                    dropped[prev][now] = true;
                    q.add(prev);
                }
            }

        }
    }
    private static void dijkstra(int first) {
        for(int i = 0;i<N;i++) {
            distances[i] = Integer.MAX_VALUE;
        }
        PriorityQueue<Road> pq = new PriorityQueue<>();
        pq.add(new Road(first, 0));
        distances[first] = 0;

        while(!pq.isEmpty()) {
            Road beforeRoad = pq.poll();
            int beforeNode = beforeRoad.node;
            int beforeEdge = beforeRoad.edge;
            if(distances[beforeNode] < beforeEdge) continue;
            List<Road> roads = map[beforeNode];
            for(Road road : roads) {
                int node = road.node;
                int edge = road.edge;
                int cost = beforeEdge + edge;
                if(distances[node] > cost && !dropped[beforeNode][node]) {
                    distances[node] = cost;
                    pq.add(new Road(node, cost));
                }
            }
        }
    }
}

간선을 제거해주는 bfs에서 중복 정점을 제거해줘야 한다.

dropped에 이미 true인 것은 continue해주었다.