[PRO] 양과 늑대

처음에 푼 풀이는 다음과 같다. 반드시 부모노드를 방문해야 그 자녀노드를 방문할 수 있고, 방문 가능한 자녀노드들은 어디서든 접근 가능하다.(방문한 곳들이 연결되어있으므로)

노드값들이 unique하므로 list가 아닌 set을 이용했다.

is_visited 대신에 possible_nodes를 통해 접근 가능한 노드들을 기록했다.
다만 전역변수를 많이 이용했는데 더 나은 방법이 있을 것 같다.(파라미터로는 변화하는 값들만 담을려고 노력했다. 정적인 값들을 전역으로)

import collections
import sys

answer = -sys.maxsize
child_node_dict = collections.defaultdict(list)
global_info = None

def dfs(now_node, possible_nodes, sheep_cnt, wolf_cnt):
    global answer
    global global_info
    
    if global_info[now_node] == 0:
        sheep_cnt += 1
    else:
        wolf_cnt += 1
    
    if sheep_cnt <= wolf_cnt: return # 잡아먹히면  안됨
    answer = max(answer, sheep_cnt)
    
    possible_nodes.update(child_node_dict[now_node])
    for next_node in possible_nodes: # 방문가능한 노드 목록
        possible_nodes.remove(next_node)
        dfs(next_node, possible_nodes.copy(), sheep_cnt, wolf_cnt) # .copy() 없으면 안됨
        possible_nodes.add(next_node)

def solution(info, edges):
    global global_info
    global answer
    global_info = info
    
    for edge in edges:
        parent, child = edge
        child_node_dict[parent].append(child)
        
    sheep_cnt = 0
    wolf_cnt = 0
    possible_nodes = set()
    dfs(0, possible_nodes, sheep_cnt, wolf_cnt)
    
    return answer