[프로그래머스] 양과 늑대 (2022 KAKAO BLIND RECRUITMENT) - Python

문제

양과 늑대

아이디어

처음엔 BFS로 접근했는데 방문 처리 시점을 어떻게 해야할지 몰라서 방황했다.
결국 DFS로 풀 수 있었다.

1. 먼저 그래프 탐색을 위해 주어진 간선 정보를 바탕으로 단방향 인접리스트를 만든다.
   트리 형식으로 주어지기도 하고, 부모 -> 자식 순서로 방문하기 때문에 단방향 인접리스트면 충분하다.
   (자식 -> 부모 방향의 탐색은 전혀 필요없다.)

2. 루트 노드인 0번을 시작으로 dfs 탐색을 한다.
   재귀 탐색 과정에서 필요한 정보는 누적 양, 누적 늑대, 방문 가능한 노드 리스트이다.

   누적 양 : 최대값 갱신을 위해 필요
   누적 늑대 : 늑대 수가 더 많은 순간 불필요한 탐색을 종료하기 위해 필요
   방문 가능한 노드 리스트 : 거쳐온 노드들의 자식 노드들을 언제든 즉시 방문할 수 있기 때문에 모든 경우의 수 탐색을 위해 필요

   처음 루트 노드 0번부터 탐색을 시작한다.

   주어진 예제 1번을 예로 들어보자.

   0번 노드를 방문했을 때 다음으로 방문 가능한 노드들은 [1, 8]이 된다.

   그 다음으로 1번 노드를 방문했을 때, 방문 가능한 노드 리스트는 1의 자식 노드 [2, 4]를 포함하여 [1, 8, 2, 4]가 될 것이다. 이 때 1번 노드는 이미 방문했던 노드이므로 리스트에 있어봤자 무의미하다.
   (물론 리스트에서 값을 제거하여 전달해도 되지만 불필요한 연산 시간이 추가될 것 같아서) visited[1]을 체크하여 중복 방문할 일을 없도록 한 뒤 재귀 호출한다. 재귀 호출이 끝난 뒤에는 다시 방문 체크를 해제하여 다음 탐색에 지장이 없도록 해야한다.

   다음으로 8번 노드를 방문했을 때, 방문 가능한 노드 리스트는 8의 자식 노드 [7, 9]를 포함하여 [1, 8, 2, 4, 7, 9]가 될 것이다. 마찬가지로 8번 노드를 방문 체크하고 재귀 호출한다.

   이와 같은 방식으로 방문 체크와 해제, 노드의 값(늑대인지 양인지)에 따라 양 개수, 늑대 개수 인자와 노드 리스트를 전달하며 dfs를 수행한다.

   또한 매 탐색마다 최대값을 업데이트 한다.
   (이 부분에서 착각할 수 있는게 늑대>= 양이 될 때만 값을 갱신하면 안된다. 늑대가 양보다 적을 때 모은 양이 가장 많다면, 거기까지만 양을 모으고 그만두면 되기 때문에 항상 최대값을 갱신해줘야 한다.)

   모든 노드들을 방문하면 탐색이 종료되고 answer에 최대값이 저장되어 있다.

전체 코드

def solution(info, edges):
    global answer
    answer = 0
    adj = [[] for _ in range(len(info))]
    visited = [0] * len(info)
    for p, c in edges:
        adj[p].append(c)
            
    def dfs(sheep, wolf, nxt):
        global answer
        if wolf >= sheep:
            return
        if sheep > answer:
            answer = sheep
        for i in nxt:
            if not visited[i]:
                visited[i] = 1
                s, w = (sheep, wolf+1) if info[i] else (sheep+1, wolf)
                dfs(s, w, nxt+adj[i])
                visited[i] = 0
                
    dfs(1, 0, adj[0])
                
    return answer