[백준/BOJ] 1916번: 최소비용 구하기

문제

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

1916번: 최소비용 구하기

해설

A번째 도시에서 B번째 도시로 가는데 필요한 최소 비용을 구하는 문제이다.

따라서 다익스트라 알고리즘을 사용하면 된다.

한 도시에서 다른 도시로 가는 버스는 다시 돌아오지 않으므로 단방향이다.

따라서 다익스트라를 진행하기 위한 그래프를 설정할 때 양방향이 아닌 단방향으로 비용을 저장해주면 된다.

다익스트라를 다 수행하고 특정 도시까지 최소 비용을 출력해도 되지만, 굳이 이럴 필요 없이 특정 도시에 도달했을 때, 다익스트라를 종료하고 그 때의 최소 비용을 출력하면 된다.

소스 코드

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

data class Info(val city: Int, val cost: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int = cost - other.cost
}

fun main() = with(System.`in`.bufferedReader()) {
    val cityCnt = readLine().toInt()
    val busCnt = readLine().toInt()
    val graph = Array(cityCnt + 1) { ArrayList<Pair<Int, Int>>() }

    repeat(busCnt) {
        val (from, to, cost) = readLine().split(" ").map { it.toInt() }
        graph[from].add(Pair(to, cost))
    }

    val (start, end) = readLine().split(" ").map { it.toInt() }
    println(dijkstra(start, end, cityCnt, graph))
}

private fun dijkstra(start: Int, end: Int, cityCnt: Int, graph: Array<ArrayList<Pair<Int, Int>>>): Int {
    val cost = IntArray(cityCnt + 1) { Int.MAX_VALUE }
    cost[start] = 0

    val pq = PriorityQueue<Info>()
    pq.add(Info(start, 0))

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curCity = cur.city
        val curCost = cur.cost

        if(curCity == end) break

        for(i in graph[curCity].indices) {
            val nextCity = graph[curCity][i].first
            val nextCost = curCost + graph[curCity][i].second

            if(nextCost < cost[nextCity]) {
                cost[nextCity] = nextCost
                pq.add(Info(nextCity, nextCost))
            }
        }
    }

    return cost[end]
}