[프로그래머스 Lv3] 모두 0으로 만들기

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

프로그래머스

트리구조를 이해하고 풀어야하는 문제.

트리에 대한 개념이 부족한 상태라서

이 문제를 통해 개념을 잡게 되었습니다.

https://school.programmers.co.kr/questions/24029

프로그래머스

문제 접근이 어려워서

제가 참고했던 질문 게시판입니다.

이 문제는 크게 2가지 스텝으로 풀었습니다.

먼저, 이 트리가 모두 0으로 만들수 있는지 없는지 여부 판단하는 것부터.

0을 최정점으로 트리를 만들었을 때,

0의 모든 리프의 값+0의 값의 합이

0이 된다면 모두 0으로 만들 수 있습니다.

이는 sum(a)=0인지 아닌지 여부로 판단할 수 있습니다.

어처피 모든 리프는 다 0이 최정점 부모이므로

모든 노드 값을 더해주면 판단이 가능.

 

저는 2번째에서 상당히 애를 먹었습니다.

자식노드 자체를 0으로 만들면서

부모노드에 값을 올려주면 되는 부분.

그런데, 어떻게 올려줘야하는지 상당히 애를 먹었습니다.

구글링을 하다가, 제가 생각한 방식과는 거리가 있는게 많아서

혼자 계속 고민하고 코드를 분석하다가

다음과 같은 방법으로 구현했습니다.

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(a, graph, per, n):
    global result
    for i in graph[n]:
        # 부모가 지정되지 않았다면 부모를 지정
        if per[i] == -1:
            per[i] = n
            # 재귀로 그 아래 자식들을 탐색
            dfs(a, graph, per, i)
            # 재귀가 끝나면, 현재 n의 자식노드 i에는 그동안 i의 자식노드에서 더해진 게 올라온다
            a[n] += a[i]
            # 서로 주고받은 값들을 더한다
            result += abs(a[i])


result = 0


def solution(a, edges):
    global result
    if sum(a) != 0:
        return -1
    answer = -2
    graph = [[] for _ in range(len(a))]
    per = [-1] * len(a)

    per[0] = -2
    for x, y in edges:
        graph[x].append(y)
        graph[y].append(x)

    dfs(a, graph, per, 0)

    return result

재귀함수에 대한 이해를 하다가

'이렇게 하면 되겠는데??'하면서

코드를 다음과 같이 구성해봤습니다.