[PG|Python] 프로그래머스 모두 0으로 만들기 - DFS

우선 -1이 나오는 경우는 a 배열을 모두 더했을 경우 = sum(a) 이 합이 0이 되지 않을 경우입니다. 이 외의 경우에는, 트리 구조이기 때문에 트리의 두 정점들을 서로 빼거나 더함으로써 반드시 0을 만들 수 있습니다.

그러면 가장 '최소가 되는' 횟수를 어떻게 찾을 수 있을까요? 이 횟수는 사실 아무런 상관이 없고 그냥 어떤 한 노드를 부모 노드로 정한 후 아래 노드까지 뻗어가서 아래 노드부터 하나씩 0으로 만들어주면 된다.

따라서 아래의 조건을 충족하기 위한 DFS를 구현하였다.

• 끝에 도달하면 ? -> 자기를 0으로 만들기 위해 부모에게 자기를 더해야 함. => Return 문 활용
• 그럼 각각의 노드는 무엇을 반환해야 해? -> 자신의 값을 반환
• 정답은 그 반환하는 전체 횟수가 중요함 -> abs(더하거나 빼는 행위의 값)

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

import sys

sys.setrecursionlimit(300000)

'''
끝에 도달하면 ? -> 자기를 0으로 만들기 위해 부모에게 자기를 더해야 함. => return문
그럼 각각의 노드는 무엇을 반환해야 해? -> 자신의 값을 반환
정답은 그 반환하는 전체 횟수가 중요함 -> abs(더하거나 빼는 행위의 값)

'''

answer = 0


def solution(a, edges):
    global answer
    if sum(a) != 0: return -1
    adj = [[] for _ in range(len(a))]
    for i in edges:
        adj[i[0]].append(i[1])
        adj[i[1]].append(i[0])
    visited = [0 for _ in range(len(a))]

    def dfs(node):
        global answer
        visited[node] = 1
        temp = 0
        for i in adj[node]:
            if not visited[i]:
                check = dfs(i)
                a[node] += check
                answer += abs(check)
                # print(check)

        return a[node]

    # print(a)
    dfs(0)
    return answer