양과 늑대(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

이진 트리 자료구조에 존재하는 양과 늑대에 대해 양의 수가 늑대의 수보다 크도록 유지하면서 양의 수의 최대값을 구하는 문제이다. 처음 시도를 할 때 그리디 문제라고 판단했는데 계속 꼬였다. 계속 시도해봤지만 안돼서 다른 분의 풀이를 보고 완전탐색으로 풀 수 있다는 것을 알게 되었다. 이진트리에서 노드를 선택시 순서에 따라 달라질 수 있다고 생각해서 완전탐색은 안되겠거니 하고 넘어갔는데 오판이었다..

 

루트 노드부터 시작하여 DFS 를 사용하여 완전 탐색을 해주면 되고, 해당 DFS 의 처리 과정은 아래와 같다.

1. 현재 동물을 판별하여 양과 늑대 개수를 업데이트 해준다.
2. 양이 늑대의 수 이하라면 재귀 함수를 종료한다
3. 늑대의 수보다 많다면
    3.1. 양의 최대 개수를 업데이트 한다
    3.2. 해당 위치의 자식들을 다음 순회할 후보에 넣어준다(현재 위치는 후보에서 제거한다)
    3.3. 갱신된 후보들에 대한 dfs를 호출한다

 

 

코드

def dfs(idx,sheep,wolf,candidates):
    global answer
	
    # 현재 위치에 대해 양과 늑대의 수를 업데이트 한다
    sheep+=animals[idx]^1
    wolf+=animals[idx]
    if sheep <= wolf: # 늑대가 양의 수 이상이라면 return 한다
        return
       
    answer=max(answer,sheep) # 양의 최대수를 갱신한다
    
    size=len(candidates)
    for i in range(size): # 현재위치의 자식 노드들을 탐색 후보에 넣어준다(현재위치는 제거한다)
        n_candidates=[candidates[j] for j in range(size) if candidates[j]!=candidates[i] ]
        n_candidates+=childs[candidates[i]][:]
        dfs(candidates[i],sheep,wolf,n_candidates)
        
    
def solution(info, edges):
    global animals,answer,childs
    animals=info
    childs=[[] for _ in range(len(info))]
    
    for parent,child in edges:
        childs[parent].append(child)
    
    answer=0
    dfs(0,0,0,childs[0][:])
    return answer

 

 

회고

1. 첫 문제 풀이 설계 부분에서 좀더 논리적일 필요가 있다
>> 생각해보니 단순히 경우의 수를 17!을 순회해야한다고 생각했고, 이 부분에서 완전탐색은 불가능하다고 생각했다. 
>> 하지만, 17!이 아니라 최대 2^16 < 10^6 이므로 완전탐색이 가능했다..

2. 재귀함수가 조금만 복잡해져도 못푸는 느낌을 받았다..연습이 필요하다