[Kotlin] 다익스트라 알고리즘 (최단경로 구하기) / 백준 1753번

다익스트라 알고리즘

• 대표적인 최단경로 알고리즘
• 특정 노드에서 출발하여, 다른 모든 노드로 가는 최단경로 계산
• 그리디로 분류 (매 상황마다 가장 비용이 적은 노드를 선택하고 이를 반복하기 때문)

동작 과정

1. 출발 노드를 설정한다
2. 최단거리 테이블을 초기화한다 (출발 노드 자기 자신 0, 나머지는 무한)
3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다
5. 3번과 4번 과정을 반복한다

Kotlin 우선순위 큐로 구현한 다익스트라 알고리즘

(백준 1753번)

import java.util.*
import kotlin.collections.ArrayList

const val INF = 1000000

fun main() {
    val input = Scanner(System.`in`)

    val n = input.nextInt() // 정점 개수
    val m = input.nextInt() // 간선 개수
    val start = input.nextInt() // 출발 노드

    val graph = Array(n+1) { ArrayList<Pair<Int, Int>>() } // 빈 그래프 생성
    val distance = IntArray(n+1) { INF }

    repeat(m) {
        // a에서 b로 가는 가중치 c 간선이 m개 만큼 존재
        val a = input.nextInt()
        val b = input.nextInt()
        val c = input.nextInt()

        graph[a].add(Pair(b, c))
    }

    fun dijkstra() {
        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second }) // (노드, 거리)

        pq.add(Pair(start, 0))
        distance[start] = 0

        while(pq.isNotEmpty()) {
            val (node, dist) = pq.poll()

            if(distance[node] < dist)
                continue

            for(nextNode in graph[node]) {
                val cost = dist + nextNode.second // 현재 거리 + 다음 노드와 연결된 가중치
                if(cost < distance[nextNode.first]) { // 이전까지 저장해둔 노드의 최단 거리와, 현재 구해둔 새로운 cost 비교
                    distance[nextNode.first] = cost
                    pq.add(Pair(nextNode.first, cost))
                }
            }
        }
    }

    dijkstra()

    for(i in 1..n) {
        if(distance[i] == INF)
            println("INF")
        else
            println(distance[i])
    }
}