2022 KAKAO Blind 양과 늑대

https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 

코딩테스트 연습 - 양과 늑대

 

 

처음 봤을 땐 그래프를 탐색(일반적인 DFS나 BFS)해가면서 모을 수 있는 최대 양을 갱신하려고 했었다.
하지만 위의 방법대로 구현하면 탐색 순서에 따라 모을 수 있는 양의 수가 달라지는 문제점이 있었다.

결정론으로 바꿔서, "해당 그래프가 주어졌을때, 탐색이 가능한가?" 에 대해 해봐도 위와 같은 문제점이 생겼다.

위의 접근법으로 어떻게든 풀려고 예시 그래프에 child node들을 덕지덕지 붙이고 떼었을 때, 다음과 같은 생각을 하게 됬다.

'양을 모을 수 있는 subtree들에서 child node를 구해가면서 답을 구하는건 어떨까?'

그래서 나는 다음과 같이 정의했다.
- tree의 모든 node를 방문했을때 tree속 양들을 모두 모을 수 있는 경우 그 tree는 양과 늑대 탐색이 가능하다고 한다.

양과 늑대 탐색이 가능한 subtree 가 주어졌을 때, subtree에 연결되어있는 child node 중 하나를 연결해 새로운 subtree를 구성하면, 새로운 subtree가 양과 늑대 탐색이 가능한지 확인하고, 이를 계속 반복하면 된다.

n <= 17이여서 subtree의 경우의 수가 30만 미만이기 때문에, 충분히 시간내에 문제를 풀 수 있다.

 

내 코드는 다음과 같다.

from collections import deque

def get_bit(bit, n): return (bit >> n) & 1
def solution(info, edges):
    answer = 0
    n = len(info)
    graph = dict()
    visited = [False] * (1<<(n+1))
    for i in range(n):  graph[i] = []
    for e in edges: graph[e[0]].append(e[1])
    
    c = deque()
    c.append(1)
    visited[1] = True
    
    while len(c):
        a = c.popleft()
        s = w = 0
        for i in range(n):
            if get_bit(a, i):
                if info[i]: w += 1
                else: s += 1
        if w >= s: continue
        answer = answer if answer >= s else s
        
        for i in range(n):
            if get_bit(a, i): 
                for child in graph[i]:
                    n = a | (1<<child)
                    if not visited[n]:
                        visited[n] = True
                        c.append(n)
    return answer