문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/92343
정리
처음 생각했던 풀이는 DFS였다. 이후 질문 게시판의 글들을 읽으며 생각이 정리되어 풀게 되었는데 DFS로 푸는 것이 틀린 것은 아니였지만 재귀함수를 어떻게 구성할 것인가에서 많이 막힌 것 같다.
DFS로 코드를 작성하면서 느꼈던 점
- 현재 노드에서 만약 오른쪽 자식노드를 탐색하고 왼쪽 자식노드를 탐색할 경우 양이 늑대보다 항상 많아 괜찮지만 반대의 경우 위반된다면 어떻게 할 것인가?
-
어떤 자식노드를 탐색한 경우라도 다시 부모노드로 돌아가 탐색할 수 있게 한다.
자식노드로 재귀함수를 호출하여도 해당 재귀함수는 다음 탐색할 노드집합에 부모노드를 포함한다. -
어떻게 보면 쉬운 풀이 같았지만 상위 노드들의 자식들도 포함시키며 재귀함수를 호출하는 것은 처음보는 유형이여서 매우 신선했다.
풀이
모든 경우의 수를 검사하는 DFS를 기반으로 한다. 하지만 양의 수가 늑대의 수보다 적어질 경우 불가능한 경우이므로 cut-off
-
방문했던 노드들은 다시 돌아올 수 있다. 하지만 돌아온다고 해서 양이나 늑대의 수의 변화는 없기 때문에 각 DFS는 방문한 노드들은 "방문 가능한 다음 노드들"이 아니다.
-
"방문 가능한 다음 노드들"은 현재 방문한 노드들과 연결된 노드들 중 방문하지 않은 노드들이다. 입력이 2진 트리로 주어지기 때문에 양방향 간선이 아닌 단방향 간선을 활용한다면 방문한 노드들과 연결된 노드들은 자식노드들만 포함시킬 수 있다.
-
DFS의 파라미터는 (양의 수,늑대의 수,방문 가능한 다음 노드들)이다.
루트노드에서부터 시작하여 루트노드와 연결된 노드들이 다음 방문 가능한 노드들이 될 것이다. 다음 방문 가능한 노드들 중 하나를 k번 노드라고 하면 다음 재귀함수의 방문 가능한 노드들은 현재 재귀함수의 방문 노드들에서 k번 노드를 제외하고 k번 노드의 자식노드들을 합친 집합이 될 것이다.
이를 통해 매 재귀함수는 탐색한 노드의 자식노드들뿐만 아니라 부모 노드나 상위 노드들의 자식노드들도 고려할 수 있으므로 모든 경우의 수를 고려할 수 있게 되는 것이다. -
탐색한 노드의 양과 늑대의 여부에 따라 양의 수와 늑대의 수를 파라미터로 넘겨주어 cut-off 여부를 확인하고 아닌 경우는 양의 수를 확인하여 모든 경우의 수에서의 양의 수 최댓값을 저장하여 리턴한다.
코드
def solution(info, edges):
global answer
answer = 0
n = len(info)
v = [[] for _ in range(n)]
for e in edges:
a,b = map(int,e)
v[a].append(b)
def dfs(sheep,wolf,next_nodes):
global answer
if sheep>wolf:
answer = max(answer,sheep)
else:
return
for node in next_nodes:
new_next_nodes = next_nodes[:]
new_next_nodes.remove(node)
for next_node in v[node]:
new_next_nodes.append(next_node)
new_sheep = sheep+1 if info[node]==0 else sheep
new_wolf = wolf+1 if info[node] else wolf
dfs(new_sheep,new_wolf,new_next_nodes)
dfs(1,0,v[0])
return answer