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

해당 문제는 다익스트라 알고리즘을 응용하여 작성할 수 있었습니다.

 

다익스트라 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 너비 우선 탐색(BFS)을 응용한 알고리즘으로, 시작 정점에서부터 거리가 가장 가까운 정점부터 탐색하면서 최단 경로를 구합니다.

알고리즘의 구체적인 동작은 다음과 같습니다.

1. 시작 정점을 선택하고, 시작 정점에서 직접 이어져 있는 모든 정점들의 거리를 계산합니다.
2. 시작 정점으로부터 거리가 가장 가까운 정점을 선택합니다.
3. 이전에 선택된 정점을 통해 직접 이어져 있는 정점들의 거리를 갱신합니다.
4. 위 과정을 모든 정점이 선택될 때까지 반복합니다.

이 알고리즘의 시간 복잡도는 우선순위 큐를 사용하여 O((E+V)logV)입니다. 여기서 E는 간선의 수, V는 정점의 수입니다.

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 사용할 수 있습니다. 음의 가중치가 있는 그래프에서는 벨만-포드 알고리즘이나 플로이드-와샬 알고리즘 등의 다른 알고리즘이 필요합니다.

 

기본적인 다익스트라 알고리즘은 최단 거리를 구하는 것이지만 해당 문제는 구해진 거리들을 우선순위큐를 사용하여 저장해놓고 만약 특정 노드의 갈 수 있는 방법이 K개가 넘는지 확인하여 넘는다면 특정 노드까지 도달하기까지의 걸린 시간중 가장 많이 걸린 시간과 현재 비교하려는 방법의 시간과 비교하여 우선순위큐에 넣어 답을 구할 수 있습니다.

 

하기는 제가 작성한 코드와 제출 결과입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

lateinit var result: Array<PriorityQueue<Int>>
lateinit var lengthlist: Array<IntArray>
var K = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())

    val N = st.nextToken().toInt() // 여행을 고려하고 있는 도시들의 개수
    val M = st.nextToken().toInt() // 도시 간에 존재하는 도로의 수
    K = st.nextToken().toInt() // 추후 K번째 최단 경로 구할 때 사용

    lengthlist = Array(N+1,{IntArray(N+1){0}}) // 도시 별 도착까지 걸리는 시간 저장

    repeat(M){
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()
        val c = st.nextToken().toInt()
        lengthlist[a][b] = c
    }

    result = Array(N+1,{ PriorityQueue<Int>(kotlin.Comparator { o1, o2 ->  o2.compareTo(o1)})}) // 도시 별 도착까지 걸리는 시간 저장

    dijkstra()

    for (i in 1 .. result.size-1){
        if(result[i].size != K) bw.appendLine("-1")
        else bw.appendLine(result[i].poll().toString())
    }

    bw.flush()
    bw.close()
}

fun dijkstra(){
    var pq = PriorityQueue<Info>(kotlin.Comparator { o1, o2 ->  o1.time.compareTo(o2.time)})
    pq.add(Info(1,0))
    result[1].add(0)

    while(!pq.isEmpty()){
        val info = pq.poll()
        val now = info.target
        val time = info.time
        for(next in 1 .. lengthlist[now].size-1){
            if(lengthlist[now][next] != 0){
                if(result[next].size < K){
                    result[next].add(time+lengthlist[now][next])
                    pq.add(Info(next,time+lengthlist[now][next]))
                } else {
                    if(result[next].peek() > time+lengthlist[now][next]){
                        result[next].poll()
                        result[next].add(time+lengthlist[now][next])
                        pq.add(Info(next,time+lengthlist[now][next]))
                    }
                }
            }
        }
    }
}

data class Info(
    val target:Int,
    val time:Int
)