[Review] 월간 코드 챌린지 시즌2 1차 3번 - 모두 0으로 만들기

모두 0으로 만들기 - Level 3

https://programmers.co.kr/learn/courses/30/lessons/76503

• 리프노드부터 0을 만들어가기
• 합의 법칙

Answer

import sys
sys.setrecursionlimit(10**9)

def solution(a, edges):
    def dfs(u, parent=None):
        answer = 0
        for child in graph[u]:
            if child != parent:
                answer += dfs(child, u)
                
        if parent is None:
            if a[u] != 0:
                return -1
        else:
            answer += abs(a[u])
            a[parent] += a[u]
            
        return answer

    graph = [[] for _ in a]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        
    return dfs(0)

graph 에 연결되는 노드들 다 넣어주기

루트 노드를 찾을 필요없이 0 부터 그냥 보면 됨 => dfs(0)

dfs 함수로 연결된 노드들 중 parent 를 제외한 노드들 확인 후 answer 에 더해주기

leaf -> root 순으로 가기 때문에 if parent is None => 더이상 계산할 값이 없음
=> a 값이 0 이 아니면 return -1

root 가 아닌 노드면 answer 에 a[u] 값 더해주고 a[parent] 값도 update

파이썬은 재귀함수 LIMIT = 3000
=> sys.setrecursionlimit(10**9) 필요