[백준 1916번] [Kotlin] 최소비용 구하기

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

1916번: 최소비용 구하기

 

난이도 : 골드 5
태그 : 그래프 이론, 데이크스트라

 

 

설명

최단경로 알고리즘 중 하나인 다익스트라 최단경로 알고리즘의 기본격인 문제입니다.

 

다익스트라(Dijkstra)가 네덜란드인이라, 네덜란드 식 발음을 살려서 읽으면 데이크스트라 정도로 읽어야 하나,

한국의 교재 등에서 다익스트라라는 표기가 더 많이 사용되는 것 같아

본 포스팅에선 '다익스트라'라는 표기를 사용하겠습니다.

 

워낙 유명한 알고리즘이다 보니, 위피디아에 잘 정리되어 있더군요.

나중에 이를 토대로 다익스트라 알고리즘 포스팅을 해야겠습니다.

 

 

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

위키피디아에 나온 다익스트라 알고리즘 수행 과정을 짧게 정리해보면,

 

1. 모든 꼭짓점을 미방문 상태로 초기화
2. 시작점을 0으로, 다른 모든 꼭짓점을 무한대로 설정
3. 현재 노드와 연결된 다른 노드 중 방문하지 않은 노드를 찾아 꼭짓점을 찾아 거리를 비교하여 더 작은 값을 넣는다.
   1.  예를 들어, 현재 노드 A의 거리가 6이고, 인접 노드 B로 연결되는 간선의 가중치가 2라고 한다면, A - B까지의 거리는 6 + 2 = 8이다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
4. 현재 노드에 인접한 노드를 모두 방문했다면, 현재 노드를 방문처리한다.
5. 두 노드 사이의 경로를 찾는 경우: 목표 노드가 방문한 상태로 표시되면 멈추고 알고리즘을 종료한다.
   
   

* 위 과정은 사이클이 존재하지 않는다는 가정하에 작성되었습니다

 

 

소스코드

 

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

val MAX_VALUE = 100000000

lateinit var distance: Array<Int>
lateinit var visited: Array<Boolean>
lateinit var weight: Array<Array<Int>>

var n = -1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    n = br.readLine().toInt() // 도시 개수
    val m = br.readLine().toInt() // 버스 개수

    weight = Array(n) { Array(n) { MAX_VALUE } }
    distance = Array(n) { MAX_VALUE }
    visited = Array(n) { false }

    repeat(m) {
        val abw = br.readLine().split(" ").map { it.toInt() }
        val a = abw[0] - 1
        val b = abw[1] - 1
        val w = abw[2]

        weight[a][b] = min(weight[a][b], w)
    }

    repeat(n) {
        weight[it][it] = 0
    }

    val goal = br.readLine().split(" ")

    val start = goal[0].toInt() - 1
    val end = goal[1].toInt() - 1

    dijkstra(start)

    println(distance[end])
}

private fun getSmallIndex(): Int {
    var min = MAX_VALUE
    var index = 0

    for (i in 0 until n) {
        if (distance[i] < min && !visited[i]) {
            min = distance[i]
            index = i
        }
    }
    return index
}

private fun dijkstra(start: Int) {
    for (i in 0 until n) distance[i] = weight[start][i]

    visited[start] = true

    for (i in 0 until n - 2) {
        val current = getSmallIndex()
        visited[current] = true

        for (j in 0 until n) {
            if (!visited[j] && (distance[current] + weight[current][j] < distance[j])) {
                distance[j] = distance[current] + weight[current][j]
            }
        }
    }
}

 

getSmallIndex() 메소드는 방문하지 않은 노드 중 코스트가 가장 낮은 노드를 찾는 메소드입니다.

 

dijkstra(start:Int) 에서는 매번 최단경로 테이블을 갱신해가며

최단경로를 찾는 과정입니다.

 

 

본 문제에서 주의할 점은, 해당 문제는 두 노드간의 거리가 입력으로 2번 이상 주어질 수도 있다는 것입니다.

따라서 입력을 받을 때, 더 짧은 간선으로 갱신하는 과정이 필요합니다.

 

 

 

후기

최단경로의 대표격인 알고리즘인 다익스트라 최단경로 알고리즘 문제였습니다

처음 다익스트라를 접했을땐, 이게 뭐지... 싶었는데, 반복해서 보니까 그래도 이제 좀 알 것 같네요.

 

사실 위 코드에서 구현한 방식은 그닥 많이 쓰이는 방법이 아닙니다.

우선순위 큐를 사용하여 개선된 방식의 다익스트라를 주로 쓰며,

위 방식은 다익스트라를 빠르게, 혹은 간단히 구현할 때에만 쓰이는 방법이라 합니다.

 

다음엔 우선순위 큐를 사용한 다익스트라 문제를 들고 오겠습니다.