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

1. 코드

from collections import defaultdict
'''
    문제: https://school.programmers.co.kr/learn/courses/30/lessons/92343
    공식 해설: https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-5-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80

    * point1: 트리 문제에서 자식노드만 방문한다는 고정관념에서 벗아나기
        자식 노드만 갈 수 있다 (x) 
        다음으로 방문할 수 있는 노드의 집합 (o)
    
        DFS(현재 노드 번호, 양의 수, 늑대의 수, 다음으로 방문할 수 있는 노드의 집합)

    * point2: 백트래킹 조건 추가
        만약 늑대가 양보다 많다면 현재 노드를 방문하는 것은 불가능하므로 
        더 이상 탐색하지 않습니다. 
'''

def solution(info, edges):
    result = [1]
    tree = defaultdict(list)
    animal_type = defaultdict(int)
    for idx, type in enumerate(info):
        animal_type[idx] = type

    for u, v in edges:
        tree[u].append(v)

    def dfs(node, sheep, wolf, path):
        print(path)
        new_sheep = sheep
        new_wolf = wolf

        """1. 현재 노드 양/늑대 확인"""
        # 현재 노드가 양 -> 양 += 1
        if animal_type[node] == 0:
            new_sheep += 1
        # 현재 노드가 늑대 -> 늑대 += 1
        else:
            new_wolf += 1

        """2. 노드 방문시 양과 늑대의 관계에 따라 최대값 갱신 or 백트래킹"""
        # 양>늑대 -> 최대값 갱신
        if new_sheep > new_wolf:
            result[0] = max(result[0], new_sheep)
        # 늑대>=양 더이상 갈 수 없음 -> 백트래킹(시간초과 TC 존재)
        else:
            return

        """3. 자식 노드 추가"""
        new_path = path[:]
        for child in tree[node]:
            new_path.append(child)

        """4. 자식 노드까지 포함된 방문 가능한 모든 노드 탐색 """
        for i in range(len(new_path)):
            dfs(new_path[i], new_sheep, new_wolf, new_path[:i] + new_path[i + 1:])

    dfs(0, 0, 0, [])
    return result[0]


print(solution([0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0],
               [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [4, 8], [6, 9], [9, 10]]))

---

2. 후기

시간 초과가 날 수 있다고 생각했는데, 풀려서 좀 의아했다.
찾아보니 공식 해설이 잘못된 해설이라는 글이 있으니 참조해도 좋을 것 같다.

• https://blog.encrypted.gg/1029