[프로그래머스] 모두 0으로 만들기 (파이썬)

난이도 : LV 3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76503

문제해결 아이디어

• 0으로 만들수 없는 경우는 -1 을 리턴해야한다.
  • sum(a) != 0 이면 -1 리턴
• DFS를 이용해서 정점을 탐색하는데, 제일 끝 정점(연결된 방문하지 않은 정점이 없는 경우)부터 0으로 만든다.
• 0으로 만들어준다는 것은 결국 자신을 dfs로 호출한 부모 정점에 자신의 가중치를 더하는 것과 같다.
• 현재 정점을 0으로 만들기 위한 연산의 횟수는 정점의 가중치의 절대값.

소스코드

import sys
sys.setrecursionlimit(10 ** 8)
ans = 0
def dfs(dep, graph, visited, node, score):
    global ans
    for i in graph[node]:
        if not visited[i]:
            visited[i] = True
            score[node] += dfs(dep + 1, graph, visited, i, score)
    ans += abs(score[node])
    return score[node]


def solution(a, edges):
    if sum(a) != 0:
        return -1

    graph = [[] for _ in range(len(a))]
    for x, y in edges:
        graph[x].append(y)
        graph[y].append(x)

    visited = [False] * len(a)
    visited[0] = True
    
    dfs(0, graph, visited, 0, a)
    
    return ans