2022 KAKAO BLIND RECRUITMENT Lv.3 양과 늑대

2022 KAKAO BLIND RECRUITMENT Lv.3

양과 늑대

루트노드 부터 탐색하여 늑대의 수가 양의 수보다 많거나 같으면 양을 다 잡아 먹음
-> 노드를 탐색하여 가장 많은 양의 수를 보유할 때 그 양의 수 return

1. 양의 수 > 늑대의 수 ?
2. 부모 노드를 방문한 적이 있는지 ?
3. 자식 노드를 처음 방문 ?

먼저 양이 늑대보다 많으면 양의 수를 결과 배열에 저장해둔다. (단, 양이 늑대보다 같거나 적으면 해당 과정을 끝냄)
그리고 edge 배열을 돌면서 방문된 부모 노드와 방문되지 않은 자식 노드 정보가 있으면,

1. 자식 노드를 방문 처리
2. 양 또는 늑대 수를 업데이트 하여 같은 과정을
3. 반복

def solution(info, edges):
    visited = [0]  # len(info) # 해당 idx 노드를 방문했는지 check
    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  # 양들이 다 잡아먹혀서 p->c 노드로 가면 안되므로

	# 루트 노드부터 시작
    visited[0] = 1
    dfs(1, 0)

    return max(answer)