[BOJ/백준] 4315 나무 위의 구슬

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    if not len(graph[node]):
        ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
        result += abs(ball_cnt_list[node] - 1)
    else:
        for next_node in graph[node]:
            dfs(next_node) 
        if parent_list[node] != -1:
            ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
            result += abs(ball_cnt_list[node] - 1)



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    parent_list = [-1 for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                parent_list[child_node] = node_num
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

 

 이 문제를 해결하는데 어려움을 겪었다.

 

이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.

 

그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.

 

현재 노드에서 1와의 차이를 부모노드로 옮겨주고,

 

그때 차이의 절대값을 결과에 계속 더해주면 된다.

 

# dotorya님 풀이

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    cnt = ball_cnt_list[node] -1

    for next_node in graph[node]:
        cnt += dfs(next_node)

    result += abs(cnt)
    return cnt



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

두 번째 풀이는 dotorya님 풀이를 복기한 것이다.

 

끝노드부터 하는 것은 동일하다.

 

그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.