[알고리즘] 프로그래머스 - 모두 0으로 만들기

프로그래머스 - 모두 0으로 만들기

다른 사람 풀이

import sys

sys.setrecursionlimit(10**6)
from collections import defaultdict

answer = 0
def dfs(cur_pos, a, tree_dict, visited):
    global answer

    visited[cur_pos] = True

    for adj_node in tree_dict[cur_pos]:
        if not visited[adj_node]:
            a[cur_pos] += dfs(adj_node, a, tree_dict, visited)
    answer += abs(a[cur_pos])
    return a[cur_pos]


def solution(a, edges):
    global answer

    if sum(a) != 0:
        return -1

    tree_dict = defaultdict(list)

    for i, j in edges:
        tree_dict[i].append(j)
        tree_dict[j].append(i)

    visited = [False] * len(a)

    dfs(0, a, tree_dict, visited)
    return answer

출처: https://velog.io/@piopiop/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AA%A8%EB%91%90-0%EC%9C%BC%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Python

처음에 그림을 보고 문제를 잘 못 이해했다. 2/0이라는게 그 노드는 최대 2까지만 담을 수 있는 것인줄 알았다.

어떻게 보면 당연한 것이지만 휴리스틱하게 받아들여야할 부분은
1. 애초에 총합이 0이 아니면 가중치를 0으로 못 만든다.
2. 총합이 0이면 가중치를 0으로 만들 수 있다.

생각보다 풀어가는 과정이 단순한데, 루트에서 시작하여 dfs를 이용해서 leaf 노드로 간다 (visited 체크를 해서 중복이 발생하지 않게 한다). leaf 노드에서 자신의 값을 호출한 함수로 던지면 된다. 그러면 그것을 받은 함수는 자신의 값을 갱신하고, 또 그보다 위의 호출 함수로 던진다.