Daily LeetCode Challenge - 2477. Minimum Fuel Cost to Report to the Capital

Problem From.

https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/

오늘 문제는 각각의 도시에서 수도인 0 으로 모일때, 좌석이 한정되어있는 차를 타고 최소의 기름을 소모하는 문제였다.
각각의 도시에서 출발하면 문제가 너무 복잡해지니, 수도인 0 에서 부터 DFS 로 각각의 도시를 모두 탐색해내었다.

각 경로의 총 사람수는 각 경로의 노드수와 같고, 각 경로를 탐색하는데에 필요한 차량의 수는
경로의 노드 수 / 차량의 좌석수 를 올림한것과 같았다.

class Solution {
    var answer = 0L
    fun minimumFuelCost(roads: Array<IntArray>, seats: Int): Long {
        val map = HashMap<Int, MutableList<Int>>()

        roads.forEach {
            map[it[0]] = map.getOrDefault(it[0], mutableListOf()).apply {
                add(it[1])
            }
            map[it[1]] = map.getOrDefault(it[1], mutableListOf()).apply {
                add(it[0])
            }
        }
        dfs(map, null, 0, seats)

        return answer
    }

    fun dfs(map: HashMap<Int, MutableList<Int>>, prev: Int?, curr: Int, seats: Int): Int {
        var passengers = 0

        map[curr]?.forEach { next ->
            if (next != prev) {
                val p = dfs(map, curr, next, seats)
                passengers += p
                answer += Math.ceil(p / seats.toDouble()).toLong()
            }
        }
        return passengers + 1
    }
}