카카오 2022 양과 늑대

파이썬

# 참고 : https://blog.encrypted.gg/1029 

ans = 1
l = [-1] * 20
r = [-1] * 20
val = []
n = 0
vis = [0] * (1<<17)

def solution(info, edges):
    global n, val
    
    # n: 전체 노드 수
    n = len(info)
    
    # val: edges 클론
    val = info[:]

    #자식 노드들 나눠서 저장, p -> l, r
    for p, c in edges:
        if l[p] == -1:
            l[p] = c
        else:
            r[p] = c 
            
    solve(1)
    
    return ans

def solve(state):
    global ans
    #탈출조건 : 현재 상태가 방문 처리 -> 종료
    if vis[state] == 1:
        return
    
    #방문 처리
    vis[state] = 1
    
    #실행
    sheep, wolf = 0, 0
    for i in range(n):
        if state & (1<<i):
            sheep += val[i] ^ 1
            wolf += val[i]
    
    #1. 늑대가 많다.
    if wolf >= sheep :
        return
    
    #2. 양이 더 많으면, max(현재 경로의 양, 기존 최대 양)
    ans = max(ans, sheep)
    
    #다음 자식으로 이동
    for i in range(n):
        #현재 상태에서 출발 하는게 아니면, continue (현재 상태가 포함되어야함)
        if not state & (1<<i):
            continue
        
        #l[출발] = 도착 /r[출발] = 도착
        if l[i] != -1:
            solve(state | 1 << l[i] )
            
        if r[i] != -1:
            solve(state | 1 << r[i] )

도저히 감이 안와서, "바킹독"이라는 분의 내용을 참고했다. (https://blog.encrypted.gg/1029)

 

어렵더라도, 해당 방법을 숙지하면 도움이 많이 될 것 같다.