2022 카카오 신입공채 코딩테스트(5)

문제링크
너무 어렵다.
백트래킹으로 문제를 풀려하면 재귀로 구현한 피보나치 수열이 어느 순간 급격하게 시간복잡도가 커지게 되는 것과 같은 현상이 일어난다. (참조)

그래서 공식 해설에서도 DFS/BFS를 소개한다. (둘 중 아무거나 상관없다고 함)
하지만 참조한 블로그에서는 비트마스킹으로 트리의 특정 부분집합에 대해 방문했는지 확인하는 방법을 사용 --> 백트래킹에 방문 여부를 추가한 것

비트마스킹으로

• {0, 1}= 3으로 0번, 1번 노드에 방문한 경우를 말한다
• {0, 1, 2} = 7 0번, 1번, 2번 노드에 방문한 경우

이런식으로 트리의 모든 부분집합을 확인하면서 양과 늑대의 수를 비교해야 한다.
그런데 양의 수가 늑대의 수 이상이면 항상 모두 수거할 수 있다.

left = [-1] * 20
right = [-1] * 20
val = []
n = 0
answer = 1
visited = [0] * (1 << 17)

def solve(state):
    global answer
    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
    
    # 현재 부분집합의 양의 수가 answer보다 클 경우 answer를 갱신
    answer = max(answer, num - wolf)
    
    for i in range(n):
        if not state & (1 << i):
            continue
        
        if left[i] != -1:
            solve(state | (1 << left[i]))
        
        if right[i] != -1:
            solve(state | (1 << right[i]))
            

def solution(info, edges):
    global n, val
    n = len(info)
    val = info[:]
    
    for u, v in edges:
        if left[u] == -1:
            left[u] = v
        else:
            right[u] = v
            
    solve(1)
    return answer

이 비트마스킹 방식이 단순히 DFS/BFS 순회에 비해 확연히 빠른 속도를 보여줬다.
위의 비트마스킹 방식은 1ms 이상 걸리는 경우를 찾을 수 없다.
아래의 DFS 방식은 한 눈에 봐도 위 경우 보다 느린 속도를 보여줬다.

---

하지만 어렵다..
DFS/BFS는 항상 알고있다고 생각하지만 문제를 못푸는 상태인 것 같다. 기본 문제를 더 풀어봐야겠다.