title: "[프로그래머스] 모두 0으로 만들기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/76503"
description: "프로그래머스 Level 3 문제 [모두 0으로 만들기]의 풀이를 정리합니다."

문제 설명 및 제한사항

문제 설명

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

제한사항

아이디어 및 해결 방법

두 점의 가중치를, 하나는 1 증가시키고 하나는 1 감소시키므로 연산 후에도 전체 트리의 가중치 합은 일정합니다.

따라서 ‘트리의 모든 노드의 가중치가 0이 될 수 있는가’의 여부는 ‘트리의 모든 노드의 가중치 합이 0인가’와 동치입니다.

우선 이 성질을 이용해서 불가능한지 여부를 판단 후 -1을 리턴하고… 더 생각해봅시다.

리프 노드의 입장에서 생각해보면, 자신의 가중치를 0으로 만드는 방법은 자신의 부모 노드로 자신의 가중치를 모두 전달하는 수 밖에 없습니다. 이 과정이 끝나면 리프 노드의 가중치는 0이 되고, 고려할 필요가 없어집니다. 그러면 리프 노드의 부모 노드를 새로운 리프 노드로 생각할 수 있고, 이 과정을 재귀적으로 반복해서 연산의 수를 구하면 될 것입니다.

자연스럽게 post-order traversal DFS를 쓰면 된다는 것을 알 수 있겠네요! Operation의 수는 자식 노드의 가중치의 절댓값이 된다는 것에 주의해서 연산의 수를 리턴하면 됩니다.

코드

from collections import defaultdict
import sys; sys.setrecursionlimit(10000000)
answer = 0

def solve(u, a, A, visited):
    global answer
    nops, val = 0, a[u]
    
    for v in A[u]:
        if v not in visited:
            visited.add(v)
            v, n = solve(v, a, A, visited)
            val += v
            nops += n + abs(v)
        
    return val, nops
            
def solution(a, edges):
    if all(x == 0 for x in a):
        return 0
    
    if sum(a) != 0:
        return -1
    
    A = defaultdict(list)
    visited = set()
    for u, v in edges:
        A[u].append(v)
        A[v].append(u)
    
    visited.add(0)
    return solve(0, a, A, visited)[1]

출처