등대

https://school.programmers.co.kr/learn/courses/30/lessons/133500

def solution(n, lighthouse):
    def make_tree():
        tree = [[] for _ in range(n + 1)]
        for a, b in lighthouse:
            tree[a].append(b)
            tree[b].append(a)
        return tree

    def dfs(node, tree, visited):
        visited[node] = True
        children = [next_node for next_node in tree[node] if not visited[next_node]]
        on, off = 1, 0
        if not children:
            return on, off
        else:
            for child in children:
                child_on, child_off = dfs(child, tree, visited)
                on += min(child_on, child_off)  # 이 부분이 포인트
                off += child_on
            return on, off

    import sys
    sys.setrecursionlimit(100_000)
    return min(dfs(1, make_tree(), [False for _ in range(n + 1)]))

테스트 1 〉	통과 (135.43ms, 35.7MB)
테스트 2 〉	통과 (133.89ms, 36.2MB)
테스트 3 〉	통과 (135.20ms, 35.7MB)
테스트 4 〉	통과 (135.13ms, 36.3MB)
테스트 5 〉	통과 (162.75ms, 36.8MB)
테스트 6 〉	통과 (157.59ms, 36.7MB)
테스트 7 〉	통과 (112.83ms, 36.7MB)
테스트 8 〉	통과 (120.25ms, 37.1MB)
테스트 9 〉	통과 (177.37ms, 47.5MB)
테스트 10 〉	통과 (126.73ms, 35.5MB)
테스트 11 〉	통과 (57.58ms, 23MB)
테스트 12 〉	통과 (32.89ms, 17.5MB)
테스트 13 〉	통과 (15.38ms, 12.6MB)
테스트 14 〉	통과 (0.01ms, 10.1MB)
테스트 15 〉	통과 (0.88ms, 10.3MB)
테스트 16 〉	통과 (4.81ms, 11.3MB)