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

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

프로그래머스

 

1. 문제설명

• 2진 트리 모양 초원에서 각 노드를 돌아다니며 양 모으기
• 각 노드는 양과 늑대로 구성
• 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양 잡아먹힘
• 중간에 양이 늑대에게 잡아먹히지 않으면서 다시 루트 노드로 돌아올 때, 최대 몇마리의 양을 모을 수 있는지 ?

 

2. 문제해결

• edges에서 하나의 edge는 부모-자식 노드의 연결을 의미한다.
• 현재 노드에서 연결된 노드들을 방문할 수 있을 뿐만 아니라 이전 부모노드에 연결된 자식노드에도 방문할 수 있다.
• 따라서 visit으로 방문 여부를 구분하고 (edges를 돌면서 부모노드는 방문하고 자식노드는 방문하지 않았으면) backtrack을 실행한다.
• 함수를 실행할 때마다 양과 늑대의 수를 체크해서 이를 처리한다.

def solution(info, edges):
    visit = [False for _ in range(len(info))]
    result = []
    def backtrack(sheep, wolf):
        if sheep > wolf:
            result.append(sheep)
        else:
            return
        
        for edge in edges:
            if visit[edge[0]] == True and visit[edge[1]] == False:
                if info[edge[1]] == 0:
                    visit[edge[1]] = True
                    backtrack(sheep+1, wolf)
                    visit[edge[1]] = False
                else:
                    visit[edge[1]] = True
                    backtrack(sheep, wolf+1)
                    visit[edge[1]] = False
    visit[0] = True
    backtrack(1, 0)
    return max(result)