백준 2307번 (java) 다익스트라

백준 2307번: 도로검문

---

관찰

1. 정점이 n개 (1000) 간선이 m개 (5000)인 가중치를 가진 양방향 간선을 가진 그래프
2. 1부터 N에 도착하기 위한 최소거리에서 얼마나 늘릴 수 있는가
3. 간선의 가중치가 양수이기 때문에 다익스트라를 활용할 수 있다.
4. 다익스트라로 기존 최소값과 간선을 하나씩 제거했을 때 최소값을 비교해서 답을 구해보자

---

시행착오

간선을 하나씩 제거했을 때 파악을 해야하는데 처음에는 이 부분을 최적화하는 방법을 몰라서 간선 5000개를 다 지워보면서 전부 다익스트라를 돌려보았다.

결국 우선순위큐를 5000번 사용하면서 메모리 초과가 나게 되었다.

---

해결 방법

그래서 간선을 제거할 때 처음에 다익스트라로 기존 최소경로를 탐색할 때 이동한 경로만을 담아서 이 간선들만 테스트 하는 방식으로 다익스트라를 돌렸다.

---

정답 코드

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

// 양방향 도로, 1번에서
// 정점 1000개, 간선 5000개
public class Main {
    public static class EdgeTest{ // 최적 경로에 있는 간선들
        int s;
        int e;
        public EdgeTest(int s, int e){
            this.s = s;
            this.e = e;
        }
    }
    public static class Edge implements Comparable<Edge>{ // 다익스트라를 위한 클래스
        int v;
        int w;
        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
        @Override
        public int compareTo(Edge o){
            return this.w - o.w;
        }
    }
    static int n, m;
    static ArrayList<Edge>[] eList;
    static long[] dist;
    static EdgeTest[] edgeList;
    static int[] prev;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        edgeList = new EdgeTest[m];
        eList = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){ eList[i] = new ArrayList<>(); };

        for(int i=0;i<m;i++){ // 기존 정보 받기
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            eList[a].add(new Edge(b,c));
            eList[b].add(new Edge(a,c));
        }

        dist = new long[n+1];
        prev = new int[n+1]; // 경로를 받기위한 자료구조
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(1,0));
        while(!pq.isEmpty()){
            Edge cur = pq.poll();
            if(cur.v == n) break;
            for(Edge next : eList[cur.v]){
                int nv = next.v;
                int nw = next.w;
                if(dist[nv] > dist[cur.v] + nw) {
                    dist[nv] = dist[cur.v] + nw;
                    prev[nv] = cur.v; // 최단 경로 기록
                    pq.add(new Edge(nv,nw));
                }
            }
        }
        int size = 0;
        for(int i = n ; prev[i] != 0 ; i = prev[i]){ // !! 경로 받은 것을 돌면서 테스트할 간선을 담아준다 !!
            edgeList[size++] = new EdgeTest(i,prev[i]);
        }

        long origin = dist[n]; // 기존 최소값
        long max = Long.MIN_VALUE; // 간선을 하나씩 막았을 때 최소값

        for(int i = 0 ;i<size;i++){ // 담은 간선들을 하나씩 제거해보면서 최대값 찾아주기 
            dist = new long[n+1];
            Arrays.fill(dist, Long.MAX_VALUE);
            dist[1] = 0;
            pq = new PriorityQueue<>();
            pq.add(new Edge(1,0));
            while(!pq.isEmpty()){
                Edge cur = pq.poll();
                if(cur.v == n) break;
                for(Edge next : eList[cur.v]){
                    int nv = next.v;
                    int nw = next.w;
                    if(cur.v == edgeList[i].s && nv == edgeList[i].e)continue;
                    if(cur.v == edgeList[i].e && nv == edgeList[i].s)continue;
                    if(dist[nv] > dist[cur.v] + nw) {
                        dist[nv] = dist[cur.v] + nw;
                        pq.add(new Edge(nv,nw));
                    }
                }
            }
            if(max < dist[n]){ max = dist[n];} // 최대값 
        }

        if(origin == Long.MAX_VALUE || max == Long.MAX_VALUE){ 
            System.out.println("-1");
        }
        else{
            System.out.println(max - origin);
        }
    }
}

---

풀이

1. 처음 다익스트라를 통해 기존 최소값과 최적 경로를 담아준다.

				// 다익스트라 함수 중간 부분
                if(dist[nv] > dist[cur.v] + nw) { 
                    dist[nv] = dist[cur.v] + nw;
                    prev[nv] = cur.v; // 최단 경로 기록
                    pq.add(new Edge(nv,nw));
                }

2. 그 후 for문을 도착지인 n 부터 0이 아닐때까지 돌려주어 테스트할 간선들을 만들어준다.

		int size = 0;
        for(int i = n ; prev[i] != 0 ; i = prev[i]){ // !! 경로 받은 것을 돌면서 테스트할 간선을 담아준다 !!
            edgeList[size++] = new EdgeTest(i,prev[i]);
        }

3. 그 후 테스트할 간선들을 하나씩 막아주면서 다익스트라로 최대값을 찾아준다!

---

한줄 정리

도로를 막아주는 경우의 수가 엄청 많았는 데 결국 어떤 도로를 막아야 하는지 생각해보는게 이번 문제에 핵심이었다.
그리고 핵심적인 부분들의 길을 찾아주고 이 길만을 테스트 해보면서 시간과 메모리를 절약할 수 있는 문제였다.
특히 다익스트라에서 prev 배열을 통해서 길을 역추적하는 것이 중요했다.