[백준] 1854번 : k번째 최단경로 찾기

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

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

 

문제 해석

항상 최단경로로 이동하는 것을 별로 좋아하지 않는다.

또한 너무 시간이 오래 걸리는 경로도 좋아하지 않아 적당한 타협안인 'k번째 최단경로'를 구하길 원합니다.

 

도시는 항상 1번부터 시작합니다.

 

첫째 줄에 n, m, k가 주어집니다.

n은 김 조교가 여행을 고려하고 있는 도시들의 개수

m은 도시 간에 존재하는 도로의 수 입니다.

 

이어서 m개의 줄에는 도로의 정보를 제공하는 정수 a, b, c가 포함됩니다.

이는 a -> b로 갈 때 걸리는 c시간을 의미합니다.

 

n개의 줄을 출력하는데 i번째 줄에는 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력해야 합니다.

최단경로에 같은 정점이 여러 번 포함되어도 됩니다.

 

문제 풀이 전 설계

특이한 점은 k번째 최단경로를 탐색해야 합니다.

다익스트라 알고리즘을 사용하면 최단경로를 탐색할 수 있는데 k번째 최단경로를 탐색하기 위해서는 다른 방법이 필요할 것 같습니다.

 

또한 간선의 개수가 200만 개이기 때문에 정점별로 최단거리를 따로 탐색하는 경우는 시간 복잡도상으로 힘들어 보입니다.

또한 최단경로에 같은 정점이 여러 번 포함되어도 되기 때문에 1 ->2 ->1 ->2 등 도시끼리 왔다 갔다 하는 경우도 존재할 수 있을 것 같습니다.

 

문제 풀이하면서

한 정점에서 다른 모든 정점의 최단거리를 구하기 때문에 다익스트라 알고리즘을 해당 풀이의 베이스로 사용해야 한다고 합니다.

 

도시(i)	1번째 최단경로 (1 →i)	2번째 최단경로 (1 →i)
1	0	-1 (존재 x)
2	2 (1→2)	10 (1→5→2)
3	6 (1→2→3)	7 (1→3)
4	4 (1→2→4)	5 (1→4)
5	6 (1→5)	14 (1→2→3→5)

 

그냥 다익스트라 알고리즘을 사용하면 1번째 최단경로밖에 구하지 못하므로 다익스트라 로직에 무언가를 첨가해주어야 합니다.

 

1) 각 도시 재방문 가능

다익스트라는 우선순위 큐를 사용하여 시작 정점과 연결되어 있는 도로 중 가장 작은 것부터 탐색을 시작합니다.

원래의 로직이라면 방문했던 도시들은 재방문하지 않아야 하지만 k번째 경로를 찾을 때까지 탐색해줘야 하므로 방문 여부를 체크하지 않습니다.

 

2) 최대 힙 배열에 최단경로 저장 및 갱신

기존 다익스트라 로직은 경로를 1차원 배열 DP에 저장하여 최단경로를 갱신합니다.

k번째의 최단경로를 저장하기 위해서는 각 DP에 사이즈가 최대 k인 힙을 입혀 최단경로를 계속 갱신해야 합니다.

따라서 N+1개의 큐를 두고 각각 최단경로를 관리합니다.

 

 

코드

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

import java.util.*;

public class Main_1854_k번째경로찾기 {

    static class EdgeInfo{
        int to;
        int time;

        public EdgeInfo(int to, int time) {
            this.to = to;
            this.time = time;
        }
    }

    static List<ArrayList<EdgeInfo>> edges = new ArrayList<>();
    static PriorityQueue<Integer>[] dpQ;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());


        for(int i=0; i<=1000; i++){
            edges.add(new ArrayList<EdgeInfo>());
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edges.get(from).add(new EdgeInfo(to,time));
        }
        //입력 끝

        //최단 경로를 쌓으면서 저장할 dpQ
        dpQ = new PriorityQueue[n+1];

        for(int i=1; i<n+1; i++){
            //최대값을 가지고있는 우선순위 큐
            dpQ[i] = new PriorityQueue<>(Collections.reverseOrder());
        }

        Queue<EdgeInfo> q = new PriorityQueue<>((c1,c2) -> (c1.time - c2.time));
        //시작점은 1으로 시작
        q.add(new EdgeInfo(1,0));
        dpQ[1].add(0); //i -> i 번째 최단경로는 0

        while(!q.isEmpty()){
            EdgeInfo curEdgeInfo = q.poll();
            int to = curEdgeInfo.to;
            int time = curEdgeInfo.time;

            for(EdgeInfo e : edges.get(to)){
                //k개의 최단 경로 저장
                if(dpQ[e.to].size() <k){
                    dpQ[e.to].add(time + e.time);
                    q.add(new EdgeInfo(e.to,e.time + time));
                    continue;
                }

                //dp[e.to].size == k일때
                //k번째 최단경로보다 현재 경로가 더 작으면 최단경로 갱신
                if (dpQ[e.to].peek() > (time + e.time)){
                    dpQ[e.to].poll();
                    dpQ[e.to].add(time +e.time);
                    q.add(new EdgeInfo(e.to,e.time + time));
                }
                //k번째 최단경로보다 현재 경로가 더 크면 q에 add되지 않고 점점 줄어들면서 종료조건으로 작용함

            }

        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<n+1; i++){
            if(dpQ[i].size() == k){
                sb.append(dpQ[i].peek() + "\n");
                continue;
            }
            sb.append(-1 + "\n");
        }

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


    }
}

 

 

 

출처

https://loosie.tistory.com/335

[BOJ] 백준 1854번 K번째 최단경로 찾기 (Java)