[프로그래머스 / python / Level 3] 양과 늑대

문제

 

2022 KAKAO BLIND RECRUITMENT 출제 문제이다.

BFS가 메인이고 상태 관리 로직이 필요하다. 카카오 문제들은 자료구조의 선택에 대해서도 많이 생각하게 된다.

 

from collections import defaultdict, deque

def solution(info, edges):
    
    """인접 딕셔너리 만들기 (부모 -> 자식 단방향)"""
    graph = defaultdict(list)
    for parent, child in edges:
        graph[parent].append(child)
    
    """큐 기본값 설정"""
    # list는 삭제/탐색연산 느려서 set 쓴다
    # 어차피 상태관리 visited로 하고 완전탐색이라 순서 상관없기에 set
    queue = deque([(1, 0, set(graph[0]))])
    
    visited = set()
    max_sheep = 1  # 루트 노드는 무조건 양이다. 최소 1마리
    
    """메인 BFS 로직"""
    while queue:
        sheep, wolf, possible = queue.popleft()
        
        # 이미 방문한 상태라면 continue
        state = (sheep, wolf, tuple(sorted(possible)))
        if state in visited:
            continue
        visited.add(state)
        
        # 양 최대 마릿수 갱신
        max_sheep = max(max_sheep, sheep)
        
        # 양, 늑대 노드 나누기
        sheep_nodes = [node for node in possible if info[node] == 0]
        wolf_nodes = [node for node in possible if info[node] == 1]
        
        # 양 노드는 전부 방문
        for node in sheep_nodes:
            new_possible = possible.copy()  # 내용물이 int(불변) 이므로 copy 안전
            new_possible.remove(node)  # 방문할 노드 삭제
            new_possible.update(graph[node])  # 방문 가능 노드 추가 (list여도 update에 의해 각각 set요소로 들어감)
            
            queue.append((sheep + 1, wolf, new_possible))
        
        # 늑대 노드는 안전할 경우 방문
        for node in wolf_nodes:
            if sheep > wolf + 1:
                new_possible = possible.copy()
                new_possible.remove(node)
                new_possible.update(graph[node])
                
                queue.append((sheep, wolf + 1, new_possible))
    
    return max_sheep

 

처음엔 백트래킹을 생각했지만, 단순 DFS/BFS로는 풀리지 않는다는 걸 알았다. 지금은 방문할 수 없지만 다른 노드를 거치고 돌아와 다시 방문하는 경우의 수도 있기 때문이다. 따라서 단순 완전탐색으로는 풀리지 않고, 상태 관리를 이용해야 한다.

 

(양의 수, 늑대 수, 방문 가능한 노드들) 을 상태로써 관리한다. 기본적으로 BFS를 진행하되, 인접 노드를 순서대로 방문하는 것이 아니라, queue에 저장된 방문 가능한 노드들을 기준으로 방문한다. 우선 다음 노드가 양이라면 무조건 방문할 수 있고, possible(방문가능 노드 집합)에서 방문할 노드를 지우고 방문할 노드와 연결된(자식) 노드를 possible에 넣는다. 이렇게 하면 노드 방문 순서에 구애받지 않고 현재 방문 가능한 노드만 선택적으로 방문할 수 있다.

 

"방문 가능 노드" 라는 건 "안전한 노드"를 의미하는 게 아니다. 안전한 노드는 방문해도 양이 잡아먹히지 않는 노드이며, 이것은 양/늑대 노드를 구분하여, 늑대 노드에 대해 sheep > wolf + 1 조건검사를 함으로써 구분한다.

 

또한 visited를 사용하는데, 여기에도 (양의 수, 늑대 수, 방문 가능한 노드들)  즉 "상태"를 넣는다. 이것은 중복된 상태, 중복된 경로 즉 중복된 경우의 수를 다시 검사하지 않게 한다.

 

이렇게 방문 가능 노드를 while문으로 방문하며, 최대 양 마릿수를 계속 갱신해 주면 된다. 뭐랄까.. 하나의 스레드가 탐색하는 느낌보다는 멀티스레드가 각각의 상태를 가지고 동시에 탐색하고 있다고 생각하면 될 것 같다. 막힌 애는 버려지고, 막히지 않은 애는 새로운 상태를 생성하고.