[programmers] 양과 늑대 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

---

bfs와 graph를 사용하려다가 틀린 문제

dfs를 통해 최대 양의 갯수를 구하면 되었다.

이때 자식 노드를 마지막엔 방문 처리를 False로 해주어 나중에 다시 그 자식 노드를 방문할 수 있게 하는 것이 중요했다.

---

def solution(info, edges):
    answer = []
    visited = [False] * len(info)
    
    
    def dfs(sheeps, wolves):
        if sheeps > wolves:
            answer.append(sheeps)
        else:
            return
        
        for p, c in edges:
            # 부모는 방문하였지만 자식은 방문 안한 경우만 진행
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheeps + 1, wolves)
                else:
                    dfs(sheeps, wolves + 1)
                # 만약 다른 곳을 들렸다 방문 시 조건에 충족할 수 있어 false 처리
                visited[c] = False
                
    visited[0] = True
    dfs(1, 0)
    
    return max(answer)