[프로그래머스][level3] 양과 늑대 - Python

문제 링크

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

프로그래머스

 

풀이

- 백트래킹 문제 

이진  트리 문제인가 싶었지만, dfs 사용하는 백트래킹 문제였다. 

평소 재귀함수를 선호하지 않아서 그런지, 완전 탐색 백트래킹 문제임을 파악하는 것이 쉽지 않다. 

 

양의 수와 늑대의 수를 매개변수로 넘겨주어, 양의 수가 늑대의 수와 같거나 클 때까지 반복한다. 

answer = 0

def dfs(sheep, wolf, edges, visited, info):
    global answer 

    if sheep > wolf :
        answer = max(answer, 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 ,edges, visited, info)
            # 늑대이면 
            else :
                dfs(sheep, wolf + 1, edges, visited, info)
            visited[c] = False 

def solution(info, edges):
    
    global answer 

    visited = [False] * len(info)
    visited[0] = True 
    # 루트는 무조건 양이므로 
    dfs(1, 0, edges ,visited, info) 

    return answer