문제 접근

카카오 코딩테스트는 그림이 항상 친절하게 주어진다. 그림도 하나의 힌트다.
그림을 보니 (심지어 문제 설명에도) 이진트리로 데이터가 주어져있다.

이진트리? 트리? 트리순회? 힙?
그래프? DFS/BFS?

그리고 입력이 info와 edges인 것을 보아 그래프 관련문제임을 "적나라"하게 드러내고있다.

info의 길이는 최대 17이므로 시간복잡도는 크게 생각하지 않았다.

그래프 구성하기

G = {}
for i in range(len(info)):
    G[i] = []
        
for edge in edges:
    src, dst = edge
    G[src].append(dst)

그래프 탐색, BFS, 그런데...

일반적인 BFS는 vertex에 연결된 edge를 따라 다른 vertex로 탐색한다. 하지만 이 문제는 약간 문제를 비틀어서 탐색한 그래프의 모든 끝 vertex들에서 탐색을 해야한다.
예를 들어, [0, 1, 4]만큼 탐색했으면, 0과 연결된 8, 1과 연결된 2, 4와 연결된 3, 6을 탐색해야 한다.

node_set = {node:0 for node in nodes} # 현재 노드집합
for node in nodes:
    for nxt in G[node]: # 연결된 모든 노드들 탐색
        if nxt not in node_set: # 현재 노드집합에 없는 노드를 탐색
            pass

나의 코드

from collections import deque

def solution(info, edges):
    answer = 0
    
    G = {}
    for i in range(len(info)):
        G[i] = []
        
    for edge in edges:
        src, dst = edge
        G[src].append(dst)

    q = deque([[[0], 1, 0]]) # [nodes, sheep, wolf]
    while q:
        nodes, sheep, wolf = q.popleft()
        answer = max(answer, sheep)
        node_set = {node:0 for node in nodes}
        for node in nodes:
            for nxt in G[node]:
                n_sheep, n_wolf = sheep, wolf
                if nxt not in node_set:
                    if info[nxt] == 0:
                        n_sheep += 1
                    else:
                        n_wolf += 1
                    
                    if n_sheep > n_wolf:
                        q.append([nodes + [nxt], n_sheep, n_wolf])
    
    
    return answer

솔직히 양궁대회보다 쉽게 빨리 풀었다. 일단 그래프 관련 문제면 lv3 깔고 시작하는 것 같다