https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=python3
문제 설명
설명이 길어서 짧게 요약하자면,
다음과 같이 양과 늑대로 이루어진 이진트리에서, 0번 노드부터 방문을 시작한다고 하자.
늑대 노드보다 양 노드를 더 많이 들려야한다고 할때, 들릴 수 있는 최대 양 노드의 수를 반환하는 문제이다.
입력으로 info, edges가 주어지고 위 예시 기준으로 다음과 같이 주어진다.
| info | edges | result |
|---|---|---|
| [0,0,1,1,1,0,1,0,1,0,1,1] | [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] | 5 |
info와 edges의 길이는 17 이하이다.
문제 해결 방법
길이가 굉장히 여유롭다.
0번부터 탐색을 시작해서 모든 경우의 수를 체크할 수 있을까?
가능해 보인다. dfs를 활용할 수 있을 것이다.
근데 일단 특정 노드 n을 방문했을 때 양 마리수는 항상 같진 않다.
문제에 방문 순서 조건이 없기 때문이다.
따라서 정답이 되는 방문 노드들을 모두 알고 있다고 하더라도, 그 순서가 중요하다.
현재 방문한 노드들을 모두 알고 있다고 가정할때, 양과 늑대의 수를 알 수 있으며 다음 방문 가능한 모든 자식 노드들을 독립적으로 방문하도록 코드를 짤 수 있다.
문제가 자원을 크게 요구하지 않아서 풀 수 있는 방법은 다양하지만 가지치기를 이용할 수 있다.
자식 노드를 방문할 때마다 방문 여부에 체크하고, 다음 자식 노드를 방문하기 전에 해당 방문 여부를 초기화하면 된다.
코드 구현
answer = 0
def solution(info, edges):
visited = [0 for _ in range(len(info))]
def dfs(s, w):
if s > w:
global answer
answer = max(answer, s)
else:
return
for par, chd in edges:
if visited[par] == 1 and visited[chd] == 0:
visited[chd] = 1
if info[chd] == 0:
dfs(s+1, w)
else:
dfs(s, w+1)
visited[chd] = 0
visited[0] = 1
dfs(1, 0)
return answer느낀점
이틀 고민하다가 다른 사람 풀이를 보고 풀었다.
어떻게 방문 순서를 알 수 있을까? 고민했는데, 사실 방문 순서따위는 중요한 게 아니였다.
완전탐색하는 방법 자체를 더 고민했더라면 쉽게 풀 수 있었을 것이다.
이와는 별개로 가지치기 << 이거 굉장히 중요한데 내가 풀 때마다 이게 있다는 사실을 망각하는 것 같다.
완전탐색을 할 땐 반드시 고려하자.
참고로 이 방법은 시간복잡도가 몇인지도 잘 모르겠다...
방법 자체가 공간을 더 크게 잡으면 dp로도 해결 가능해보인다.
나중에 여유있으면 해보자.
