Daily LeetCode Challenge - 787. Cheapest Flights Within K Stops

Problem From.

https://leetcode.com/problems/cheapest-flights-within-k-stops/

오늘 문제는 주어진 배열에서 출발지 src 도착지 dst 경유할 수 있는 도시의 수 k 가 주어졌을때, 각각의 도시를 경유할 경우의 가장 작은 cost 를 구하는 문제였다.

제일 까다로운 부분은 주어진 배열을 graph 형식으로 만드는 거였는데, 출발지를 기준으로 도착지와 각각의 도시로 가는 비용을 원소로 하여 그래프를 만들었다.
나머지는 BFS 를 이용하여, 해당 도시까지 도착하는 가장 적은 cost 를 반환하도록 만들었다.

class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {

        val graph: Array<MutableList<IntArray>> = Array(n) { mutableListOf<IntArray>() }
        for ((from, to, cost) in flights) {
            graph[from].add(intArrayOf(to, cost))
        }


        var cheapest = IntArray(n) { Int.MAX_VALUE }
        var queue = LinkedList<IntArray>()
        queue.add(intArrayOf(src, 0, -1))
        while (queue.isNotEmpty()) {
            val (loc, cost, stops) = queue.poll()
            if (stops > k || cost >= cheapest[loc]) {
                continue
            }
            cheapest[loc] = cost
            for ((dest, price) in graph[loc]) {
                queue.add(intArrayOf(dest, cost + price, stops + 1))
            }
        }
        return if (cheapest[dst] == Int.MAX_VALUE) -1 else cheapest[dst]
    }
}