[leet112] PathSum. 함수 속 변수가 함수 밖에 영향을 주지 않는다

함수 속 변수 변화는 함수 밖에 영향을 주지 못한다

global, local variables. 너무 당연한 이야기이지만 재귀적으로 함수를 구현하면서 고민이 됐던 부분이 있었다. 이 문제는 간단한 DFS로 해결이 가능하니 고민 포인트를 코드와 함께 간단히 메모해둔다.

Question

root to leaf의 합 중 targetSum 값과 같은 값이 있다면 (즉 leaf까지 모두 더했을 때 targetSum을 만들 수 있다면) True, 그렇지 않다면 False

Solution

평소 DFS를 사용할 때와 다른 점이 있었다. 아래 코드에서의 ans처럼 path라든지 어떤 목표 데이터들을 helper 밖에서 정의하고 helper는 nonlocal로 그 변수를 가져와서 업데이트 해주면서 recursion을 돈다.
그러나 여기서는 path의 합이 돼야 하기 때문에 path가 끝나면 이전으로 돌아가야 한다. 코드와 함께 보자면, #checkpoint!!! 부분. temp_sum이 인자로 받아지는 것이 아니라 nonlocal로 업데이트를 하는 방식이라면 for loop의 앞선 연산에서 nonlocal temp_sum이 바뀌어버리기 때문에 다시 해당시점의 값으로 되돌리기 어려울 것이다.
쉽게 위 example 그림으로 예를 들자면, 11->7로 가서 계산 후에 다시 11->2로 돌아가야 하는데 temp_sum 값은 이미 7까지 더해진 상태인 것이다. 7만 빼준다고 될 일도 아니다. 오른쪽 8->4->1 경우엔 다시 8->13으로 가려면 4와 1을 빼줘야 하는 것이니...

하지만 이 코드가 동작할 때 dfs_helper(7, 20)이 돌아간 후 다음 element로 명령을 내렸던 dfs_helper(2, temp_sum)에서 또한 temp_sum은 20으로 동작한다. 27이 아니다.

왜? dfs_helper(7, 20)에서의 temp_sum이 바뀌었을 뿐 그 함수 바깥에서의 temp_sum은 바뀌지 않았기 때문이다. 괜히 고민을 많이 했었는데 기본적으로 당연한 부분이었다. 역시 기본이 탄탄해야...

def hasPathSum(root, targetSum):
    if not root: return False
    ans = False

    def dfs_helper(root, temp_sum):
        nonlocal ans, targetSum
        temp_sum += root.val
        if not root.left and not root.right:
            if temp_sum == targetSum:
                ans = True
            return
        
        togo = [node for node in [root.left, root.right] if node]
        for node in togo:
            #cur_sum = temp_sum
            dfs_helper(node, temp_sum) # checkpoint!!!
    dfs_helper(root, 0)
    return ans