Programmers - 양과 늑대 (level3)

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/92343

문제 설명

2진 트리 모양의 초원, 각 노드에는 양 또는 늑대가 있다.
노드를 방문하면 거기에 있는 동물을 데리고 가는데 만약 늑대의 수가 양의 수와 같거나 많아지면 잡아먹는다.
이진탐색 모든 경우에 최대로 데려올 수 있는 양의 수를 구하여라.

각 노드마다 늑대 수와 최대 양의 수를 저장하며 탐색하자.
처음에는 늑대 -1, 양 +1이라고 잘못 생각해서 한참 헤매다가 늑대와 양의 수를 따로따로 생각해야 한다는 걸 깨닫고 모든 탐색 경우의 수를 체크하는 bfs 방식으로 구현을 했다.
하지만 전체 탐색이 아니므로 정답보다 작게 나왔고, 결국 구글링하여 이 문제는 dfs로 풀어야한다는 걸 깨달았다.
가장 쉬운 방법은 늑대가 양보다 적다는 조건으로 dfs로 탐색하며 방문 여부를 체크, 양의 Max 값을 찾는 것이다.
코드는 아래와 같다.

def solution(info, edges):
    visited = [False for _ in range(len(info))]
    result = []
    
    def dfs(sheep, wolf):
        if sheep > wolf:
            result.append(sheep)
        else:
            return
        
        for p, c in edges:
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheep+1, wolf)                
                else:
                    dfs(sheep, wolf+1)
                visited[c] = False
    visited[0] = True            
    dfs(1,0)
    result.sort(reverse=True)            
    return result[0]

회고

자꾸 풀이가 섬으로 가고 복잡해진다. 문제를 더욱 꼼꼼히 보고 솔루션을 그려본 후 코드를 작성하자.
BFS가 익숙해져서 익숙한 방법으로 풀게 되는데 DFS로 풀어야 하는 유형을 다시 익혀야겠다.