[프로그래머스] 양과 늑대 (파이썬)

난이도 : LV 3

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

문제해결 아이디어

• 문제푸는 방법을 모르겠어서 다른사람의 풀이를 참고했다.
• 생각보다 코드가 간단해서 놀랬는데 핵심은
  • 부모노드를 방문했지만 아직 방문하지 않은 자식노드들을 탐색하는것 이였다.

소스코드

def solution(info, edges):    
    ans = []
    visited = [0] * len(info)
    def dfs(sheep, wolf):
        if wolf >= sheep:
            return
        else:
            ans.append(sheep)
            
        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(ans)