[6개월 안에 백준 플래티넘 달성하기] 9. 최소비용 구하기 1916

코딩테스트/백준 코틀린

[6개월 안에 백준 플래티넘 달성하기] 9. 최소비용 구하기 1916 | 코틀린

junjunjun 2023. 11. 27. 22:45

Class 4에서 처음으로 접하게 된 그래프 알고리즘인 다익스트라 문제입니다.

다익스트라의 기본 개념을 알고 있고 몇 개의 반례 케이스만 해결한다면 쉽게 풀 수 있습니다.

문제

풀이

사실 다익스트라에 대한 개념이 없어도 bfs + 우선순위 큐 를 잘 활용하면 문제를 풀 수 있습니다.

A에서 B까지의 최소 비용을 구하기 위해서는 결국 A에서부터 BFS로 최소 비용을 구하면서 B에 도달하면 됩니다.

추가적으로 주의해야 할 반례 케이스가 두 가지 있습니다.

첫 번째로 버스 비용이 0인 경우가 가능합니다. 따라서 초기화 시점에 값을 0으로 지정하면 안 됩니다.
두 번째로 동일한 버스 노선에 여러 비용을 주는 경우가 있습니다. 이 경우에는 여러 비용 중 최소 비용을 추가하도록 코드를 수정해 주면 됩니다.

반례 모음

import java.io.StreamTokenizer
import java.util.PriorityQueue

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input()
    val M = input()
    val arr = Array(N+1) { IntArray(N+1) {Int.MAX_VALUE} } // 비용이 0인 경우도 있기에 MAX로 초기화

    repeat(M) {
        val start = input()
        val end = input()
        val cost = input()
        // 동일한 버스노선인 경우 최소 비용을 선택
        if (arr[start][end] > cost) {
            arr[start][end] = cost
        }
    }

    val visited = BooleanArray(N+1)              // 도시 방문 여부
    val minCost = IntArray(N+1) {Int.MAX_VALUE}  // 시작 지점에서 각 도시별 최단 비용

    val start = input()
    val end = input()

    class Node(val number: Int, val edge: Int)  // (도시, 비용)
    
    val queue = PriorityQueue<Node>(compareBy { it.edge })  // 최소 비용 우선순위 큐
    queue.add(Node(start, 0))
    minCost[start] = 0
    
    while (queue.isNotEmpty()) {
        val poll =queue.poll()
        val number = poll.number

        if (visited[number]) continue
        visited[number] = true
        
        for (i in 1..N) {
            // i 도시까지 경로가 존재할 때
            if (arr[number][i] != Int.MAX_VALUE) {
                // 기존 비용보다 적은 비용이 드는 경우 업데이트
                if (minCost[i] > arr[number][i] + minCost[number]) {
                    minCost[i] = arr[number][i] + minCost[number]
                    queue.add(Node(i, minCost[i]))
                }
            }
        }
    }
    print(minCost[end])
}

이렇게만 보면 우선순위 큐가 굳이 사용될 이유가 있을까 싶습니다. 하지만 비용을 신경 쓰지 않고 큐에 담을 경우 최소 비용의 노선으로 업데이트된다 하더라도 이미 방문한 노드일 경우 추가적인 업데이트가 불가능해지는 경우가 발생합니다.

예시를 보면