양과 늑대

from collections import defaultdict N = 0 ans = 0 val = [] A = defaultdict(list) visited = [False] * (1 << 17) def solve(state): global ans, A if visited[state]: return None visited[state] = 1 # 해당 상태가 얼마나 많은 정점을 보고 있는지, # + 늑대 수는 얼마나 되는지 계산한다. wolf, num = 0, 0 for i in range(N): if state & (1 << i): num += 1 wolf += val[i] # 늑대가 절반 이상이면 옳지 않은 상태이다. if 2 * wolf >= num: return None # ans를 업데이트 한다. ans = max(ans, num - wolf) # 다음 상태를 점검한다. # 해당 state에 포함된 모든 정점에 대해서, 자식 노드 하나씩 추가해보면서 for u in range(N): if not state & (1 << u): continue for v in A[u]: solve(state | (1 << v)) def solution(info, edges): global A, N, val N = len(info) val = info[:] # Edge list for u, v in edges: A[u].append(v) solve(1) return ans