양과 늑대 [2022 KAKAO BLIND RECRUITMENT]

1. 문제 접근 방법

- 이 문제는 DFS를 활용하되, 일반적인 백트레킹으로 접근하면 안되는 문제이다.

  edges에는 부모, 자식 노드가 순차적으로 저장되어 있는데, 

  1) 자식 노드는 반드시 부모 노드를 방문해야 방문할 수 있음

  을 활용해서 코드를 작성한다 

  그리고 한 번 방문한 자식 노드는 방문 처리를 해준다. 

 

- 그리고 edges에 대해 탐색을 할 때, 항상 첫번째 edge부터 순차적으로 탐색을 해야 함을 기억한다. 

 

2. 소스 코드

def solution(info, edges):
    
    visited = [0] * len(info)
    answer = []
    
    def dfs(sheep, wolf):
        
        if sheep > wolf:
            answer.append(sheep)
        else:
            return 
        
        for p, c in edges:
            if visited[p] and not visited[c]:
                
                visited[c] = 1
                if info[c] == 0:
                    dfs(sheep+1, wolf)
                else:
                    dfs(sheep, wolf+1)
                visited[c] = 0


    visited[0] = 1
    dfs(1, 0)

    return max(answer)