[백준][KOTLIN] 13308 주유소

- https://www.acmicpc.net/problem/13308

13308번: 주유소

풀이

1. 각 도로의 거리가 가중치가 있다 : 다익스트라 알고리즘 이용

2. 각 도시의 주유비가 다르다 : 각 도시까지 주유비에 따른 최소 비용을 저장하는 동적 프로그래밍(dp[i][j] : i 도시까지 j 주유비로 가는 최소 비용)

 

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    // N : 도시의 개수
    // M : 도로의 개수
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val cost = IntArray(N + 1)

    val inputCost = br.readLine().split(" ").map { it.toInt() }.toIntArray()

    inputCost.forEachIndexed { index, value ->
        cost[index + 1] = value
    }

    val g = Graph(N)

    repeat(M) {
        val (s, e, d) = br.readLine().split(" ").map { it.toInt() }.toIntArray()
        g.input(s, e, d)
    }

    println("${g.dijkstra(1, cost)}")
}

private class Graph(private val n: Int) {
    val adjList = Array(n + 1) {
        mutableListOf<Road>()
    }

    fun input(start: Int, end: Int, distance: Int) {
        adjList[start].add(Road(end, distance))
        adjList[end].add(Road(start, distance))
    }

    fun dijkstra(start: Int, oilCost: IntArray): Long {
        // cost[i][j] => i : 현재 도시 정보, j : 주유소 최소 가격, 결과 : 최소 비용
        val cost = Array(n + 1) {
            LongArray(2501)
        }

        repeat(n + 1) {
            Arrays.fill(cost[it], Long.MAX_VALUE)
        }

        val queue = PriorityQueue<OilCost>()
        queue.add(OilCost(start, oilCost[start], 0))

        while (!queue.isEmpty()) {
            val current = queue.remove()
            val currentIdx = current.idx
            val currentMinCost = current.minCost
            val currentTotalCost = current.totalCost

            if (currentIdx == n) return currentTotalCost

            for (road in adjList[currentIdx]) {
                if (cost[road.to][currentMinCost] > currentTotalCost + road.distance * currentMinCost) {
                    cost[road.to][currentMinCost] = currentTotalCost + road.distance * currentMinCost
                    queue.add(OilCost(road.to, min(currentMinCost, oilCost[road.to]), cost[road.to][currentMinCost]))
                }
            }
        }

        return -1L
    }

    fun min(a: Int, b: Int): Int {
        return if (a > b) b else a
    }
}

private data class Road(val to: Int, val distance: Int)

private class OilCost(val idx: Int, val minCost: Int, val totalCost: Long): Comparable<OilCost> {
    override fun compareTo(other: OilCost): Int {
        return when {
            totalCost - other.totalCost > 0L -> 1
            totalCost - other.totalCost < 0L -> -1
            else -> 0
        }
    }
}