[LeetCode] 2477. Minimum Fuel Cost to Report to the Capital

- Problem

2477. Minimum Fuel Cost to Report to the Capital

- 내 풀이 1 (DFS)

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        def dfs(node: int, parent: int = -1) -> int:
            cities = 1

            for nei in graph[node]:
                if nei != parent:
                    cities += dfs(nei, node)
            
            if node:
                self.answer += ceil(cities / seats)
            
            return cities

        graph = defaultdict(list)
        self.answer = 0

        for x, y in roads:
            graph[x].append(y)
            graph[y].append(x)
        
        dfs(0)

        return self.answer

- 결과

- 내 풀이 2 (BFS, Topological Sort)

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        graph = defaultdict(list)
        degrees = defaultdict(int)
        cities = defaultdict(lambda: 1)
        costs = 0

        for x, y in roads:
            graph[x].append(y)
            graph[y].append(x)
            degrees[x] += 1
            degrees[y] += 1

        q = deque([city for city, degree in degrees.items() if city and degree == 1])

        while q:
            city = q.popleft()
            costs += ceil(cities[city] / seats)

            for nei in graph[city]:
                cities[nei] += cities[city]
                degrees[nei] -= 1
                if nei and degrees[nei] == 1:
                    q.append(nei)
        
        return costs

- 결과