title: "[프로그래머스] 양과 늑대 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/92343"
description: "프로그래머스 Level 3 문제 [양과 늑대]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

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

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges