1443. Minimum Time to Collect All Apples in a Tree (Hash Table, Tree, Depth-First Search, Breadth-First Search)

링크 - https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

먼저 양방향 그래프를 만들어야 한다. 그다음 dfs를 통해 사과가 있을때마다 2를 더하는 식으로 답을 풀어야 한다.

Code

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        graph = defaultdict(list)
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        def dfs(node, parent):
            total_time = child_time = 0
            for child in graph[node]:
                if child == parent:
                    continue
                child_time = dfs(child, node)
                if child_time > 0 or hasApple[child]:
                    total_time += child_time + 2

            return total_time

        return dfs(0, -1)

Complexity

Time Complexity: O(n)

Space Complexity: O(n)