[백준 / BOJ] 5719 거의 최단 경로 (Java)

문제

출처 : https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

N개의 장소와 M개의 도로가 주어진다.

(각 도로는 가중치를 갖고있다.)

 

시작도시 S에서 도착도시 D로 가는 최단경로를 포함하지않는 경로중 가장 빠른 경로를 출력하는 문제다.

---

풀이

쉬운 문제이해와 그렇지 않은 최적화 과정..

다익스트라로 푸는 문제였다.

 

문제가 특이한게, 플래티넘 난이도 임에도 푸는 방법이 굉장히 직관적으로 보인다.

최적화와 경로 추적이 어려워서 플래티넘 난이도를 받은것같다.

 

로직

1. 다익스트라를 한번 수행해 최단경로 간선을 모두 찾는다.

2. 1번에서 찾은 최단경로 간선을 없앤다.(나는 2차원 boolean배열이 true라면 해당 간선은 더 이상 이용못하는 간선으로 구현했다.)

- path[a][b] = true // a -> b 로 가는 간선은 더 이상 이용못함.

3. 다익스트라를 한번 더 수행해 최단경로를 찾는다.

 

다익스트라

로직 1, 로직 2를 한번에 수행하는 다익스트라 코드다.

기본 다익스트라에서 경로 추적만 추가했기때문에 설명은 생략하겠다.

소스코드

    private int dijkstra(){
        int ans = 987654321;
        PriorityQueue<Position> pq = new PriorityQueue<Position>();
        pq.add(new Position(0, S, S));
        int[] check = new int[N+5];
        boolean[][] del = new boolean[N+5][N+5];
        for(int i = 0; i <= N; i++) check[i] = 987654321;
        check[S] = 0;
        while(!pq.isEmpty()){
            int nowIdx = pq.peek().idx;
            int nowCost = pq.peek().cost;
            int parIdx = pq.peek().parIdx;
            pq.poll();
            if(nowCost > ans) break; // 최적화
            if(check[nowIdx] < nowCost) continue;
            if(!del[nowIdx][parIdx]) par.get(nowIdx).add(parIdx); // 최적화
            del[nowIdx][parIdx] = true;
            if(nowIdx == D){
                ans = nowCost;
                continue;
            }
            for(int i = 0; i < edge.get(nowIdx).size(); i++){
                Position p = edge.get(nowIdx).get(i);
                int nextIdx = p.idx;
                int nextCost = nowCost + p.cost;
                if(nextCost > check[nextIdx] || path[nowIdx][nextIdx] == true) continue;
                if(nextCost == check[nextIdx]){ // 최적화
                    if(!del[nextIdx][nowIdx]) par.get(nextIdx).add(nowIdx);
                    del[nextIdx][nowIdx] = true;
                    continue;
                }
                check[nextIdx] = nextCost;
                pq.add(new Position(nextCost, nextIdx, nowIdx));
            }
        }
        if(ans == 987654321) return -1;
        return ans;
    }

경로 추적

DFS로 구현했으면 쉬웠을 경로 추적이 BFS로 구현해서 어려워졌다.

DFS로 다익스트라를 구현할경우, 최악의 경우 N^2이 나와서 TLE를 맞을수도 있기 때문에, PriorityQueue를 이용해 구현했다. 

 

문제를 풀기위해 최단경로값을 갖는 모든 경로를 알아야한다. 즉, 아래와 같이 하나의 부모노드에 여러개의 자식노드가 올수있다.

- 2 -> 1

- 3 -> 1

- 4 -> 1

 

BFS로 구현했기때문에, 2차원 배열을 통해서 이를 표현해줘야한다.

(편의를 위해 2차원 행렬로 설명하지만, 나는 수행 시간을 줄이기위해 2차원 ArrayList로 구현했다.)

par[부모노드][현재노드] = true // 값이 true라면 간선이 존재하는것임

- par[1][2] = true

- par[1][3] = true

- par[1][4] = true

이후, par배열을 역추적하며 경로를 없애주면 된다.

 

소스코드

    private void setPath(int idx){
        if(idx == S) return;
        for(int i = 0; i < par.get(idx).size(); i++){
            int nextIdx = par.get(idx).get(i);
            if(path[nextIdx][idx]) continue; // 최적화 
            path[nextIdx][idx] = true;
            setPath(nextIdx);
        }
    }

위 코드의 최적화 주석이 있는곳처럼 이미 해당 경로를 없앴다면 더 이상 탐색하지 않도록 해야한다.

(저 부분이 없으면 시간초과 나옴)

---

전체 소스코드 

https://github.com/devxb/JJUNalgo/blob/master/5719%20%EA%B1%B0%EC%9D%98%20%EC%B5%9C%EB%8B%A8%20%EA%B2%BD%EB%A1%9C/Main.java

devxb/JJUNalgo