[Python] 프로그래머스 / 월간 코드 챌린지 시즌2 / 모두 0으로 만들기

문제 링크

 

DFS에서 이따금씩 쓰이는 nonlocal 선언

def outer():
    x = 10
    
    def inner():
        x += 5  

    inner()
    print(x)
    
outer()

"""
---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)
<ipython-input-5-0811df1b6f71> in <cell line: 1>()
----> 1 outer()

1 frames
<ipython-input-4-c65dcae4dbf8> in inner()
      4     def inner():
      5         #nonlocal x  # 바깥 함수의 x 변수에 접근
----> 6         x += 5  # x에 새로운 값을 할당
      7 
      8     inner()

UnboundLocalError: local variable 'x' referenced before assignment
"""

def outer():
    x = 10
    
    def inner():
        nonlocal x
        x += 5  

    inner()
    print(x)

outer()	#15

 

global 선언과 다른 점:

• global은 전역 범위 변수를 함수 내부에서 재할당할 때
• nonlocal은 외부 함수의 지역변수를 내부 함수에서 재할당할 때

 

트리 구조의 특수성

놓치기 쉬운 지점일 수 있지만, 이 그래프가 트리 구조라는 데에 주목하자. 트리 구조는 노드 A에서 노드 B로 가는 길이 하나이다. 그러므로 어느 경로가 더 최적인지 다이크스트라 등을 써서 파악할 필요 없이, 리프노드부터 자기 자신을 0으로 만들면서 자기 자신의 값을 부모에게 쌓아올리는 것이다.

 

*어디가 리프노드이고 어디가 루트노드인지는 우리의 임의 선택에 따라 정해진다. 애초에 트리 구조는 어디든 리프가 될 수 있고, 어디든 루트가 될 수 있기 때문.

 

정답 코드

import sys
sys.setrecursionlimit(300000)

def solution(a, edges):
    
    if sum(a) != 0 :
        return -1
    
    n = len(a) 
    tree = [[] for _ in range(n)]
    
    for s, e in edges :
        tree[s].append(e)
        tree[e].append(s)
        
    seen = [False] * n
    answer = 0
    
    def dfs(node) :
        nonlocal answer
        
        seen[node] = True
        c = a[node]
        
        for neighbor in tree[node] :
            if not seen[neighbor] :
                c += dfs(neighbor)
        
        answer += abs(c)
        return c
    
    dfs(0)
    
    return answer