2023.02.12 Today's Challenge

fabichoi 2023. 2. 12. 23:45

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

Minimum Fuel Cost to Report to the Capital - LeetCode

Can you solve this real interview question? Minimum Fuel Cost to Report to the Capital - There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads.

leetcode.com

오늘은 DFS 문제!

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        ans = 0
        graph = [[] for _ in range(len(roads) + 1)]

        for u, v in roads:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(u, prev):
            nonlocal ans
            people = 1
            for v in graph[u]:
                if v == prev:
                    continue
                people += dfs(v, u)
            if u > 0:
                ans += int(math.ceil(people/seats))
            return people

        dfs(0, -1)
        return ans