PROGRAMMERS 양과 늑대

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

input :

• 2 ≤ info의 길이 ≤ 17
• info의 원소는 0은 양, 1은 늑대
• edges의 각 원소의 형태 : [부모 노드 번호, 자식 노드 번호]

output :

• 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return

조건 :

• 루트 노드에서 출발
• 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어

---

idea

해설

DFS를 통해 문제를 해결하려함. 이 경우 basecase를 잘 따져야 하는데 이를 놓침.

주의

2번에 해당하는 경우를 놓친 것이 시간을 많이 소요한 이유였음.
temp에 복사를 해서 not_visited를 동일한 형태로 유지해야 하는 것도 주의 해야함.

def solution(info, edges):
    graph = [[] for _ in range(len(info))]

    def dfs(node, sheep, wolf, not_visit):
        sheep += 1 if not info[node] else 0
        wolf += info[node]
        if sheep <= wolf:
            return sheep

        ans = 0
        for next_node in range(len(not_visit)):
            if not not_visit[next_node]:
                continue

            temp = [i for i in not_visit]
            temp[next_node] = 0
            for idx in graph[next_node]:
                temp[idx] = 1
            ans = max(ans, dfs(next_node, sheep, wolf, temp))

        return max(sheep, ans)

    for a, b in edges:
        graph[a].append(b)

    not_visit = [0] * len(info)
    for idx in graph[0]:
        not_visit[idx] = 1

    return dfs(0, 0, 0, not_visit)