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

https://programmers.co.kr/learn/courses/30/lessons/76503

코딩테스트 연습 - 모두 0으로 만들기

 

DFS 문제다. queue로 BFS 풀려했는데 잘 풀리지 않았다

DFS 방식이 좀 친숙해지는 계기가 된 것 같다.

 

import sys
sys.setrecursionlimit(300000)
answer =0

def solution(a,edges):
    global answer
    if sum(a) !=0:
        return -1
    graph = [[] for _ in range(len(a))]
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    
    def dfs(now,pre):
        global answer
        for next in graph[now]:
            if next != pre:
                dfs(next,now)
        answer += abs(a[now])
        a[pre] += a[now]
        a[now] -= a[now]
    dfs(0,0)
    return answer