양과늑대

이진트리의 각노드에 양 0,늑대1 둘중하나가 있고 
루트노드(무조건양) 에서 출발해서 노드들을 돌아다니면 양을 모아야하는데 양의수<=늑대수 이면
양이 잡아먹힘  최대모을수 있는 양의 수 구하기

info[i] 에 i 노드에 양이 있는지 늑대가 있는지 
edges에 각노드의 연결정보들 나열 [부모노드,자식노드]

 

<집합에서 update역할: 기존의 것은 그대로 놔두고 update할 요소 추가>

# 기존 집합
a = {1, 2, 3}
# 추가할 집합
b = {3, 4, 5}

# 집합 a를 업데이트
a.update(b)

print(a)  # 출력: {1, 2, 3, 4, 5}

 

 

 

def solution(info, edges):
    max_v = 0
    graph = [[] for _ in range(len(info))]
    for edge in edges:
        graph[edge[0]].append(edge[1])
    # return graph [[1, 8], [2, 4], [], [], [3, 6], [], [5], [], [7, 9], [10, 11], [], []]
    queue = [(0,1,0,set())] # (현재노드위치,양의수,늑대수) 큐에 담기

    while queue:
        current_node,sheep,wolf,visited = queue.pop(0)
        if max_v < sheep:
            max_v = sheep
        visited.update(graph[current_node])

        for i in visited:
            if info[i] == 1: # 늑대라면
                if sheep > wolf+1:
                    queue.append((i,sheep,wolf+1,visited-{i}))
            else:
                queue.append((i,sheep+1,wolf,visited-{i}))
    return max_v