[백준 / BOJ] 1854 K번째 최단경로 찾기

문제

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

1854번: K번째 최단경로 찾기

n개의 도시, m개의 길, k가 주어진다.

김 조교가 1번째 도시에서 출발한다 했을때,

1번부터 n번도시까지 k번째 최단경로를 구하는 문제다.

 

---

풀이

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

k가 100으로 크지않아서, n번째 도시에 k번째 도착하는 모든 경로를 찾아서 구해주면된다.

 

로직

1. 1번도시에서 다익스트라를 시작한다.

2. 최단경로라고 종료하는것이 아닌, i(1 <= i <= n)번째 도시에 도착하는 k번째 경로를 모두 찾아준다.

 

다익스트라 소스코드

    private void dijkstra(){
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
        pq.add(new Edge(0, 1));
        costCheck[1] = 0;
        while(!pq.isEmpty()){
            int nowNode = pq.peek().node;
            int nowCost = pq.peek().cost;
            pq.poll();
            if(cand.get(nowNode).size() >= k) continue;
            cand.get(nowNode).add(nowCost);
            for(int i = 0; i < edges.get(nowNode).size(); i++){
                int nextNode = edges.get(nowNode).get(i).node;
                int nextCost = nowCost + edges.get(nowNode).get(i).cost;
                if(costCheck[nextNode] == nextCost || cand.get(nextNode).size() >= k) continue;
                pq.add(new Edge(nextCost, nextNode));
            }
        }
    }

소스코드를 보면 기저조건이 cand.get(nextNode).size() >= k로 일반 다익스트라와 다른것을 볼수있다.

cand는 i번째 도시에 도착한 k개 간선들의 가중치들을 저장한 리스트이다.

 

시간복잡도를 구하기가 까다로웠다.

n,m,k가 전부 최대일때,

하나의 노드에서 최대 k개의 간선이 파생될수있다.

즉, k^n으로 시간복잡도를 생각할수있는데, 모든 노드들이 받아들일수있는 최대 간선이 100개이므로, 실 시간복잡도는 이것보다 훨씬 작다.

한 노드가 최대 k번 나올수 있으므로, 최종 시간복잡도는 아래와 같을것이라 생각한다.

O(k * mlog(k*n));

 

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1854%20K%EB%B2%88%EC%A7%B8%20%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C%20%EC%B0%BE%EA%B8%B0/Main.java

devxb/JJUNalgo