[BOJ 13325, Python] 이진 트리

문제 링크

BOJ 13325

분류

다이나믹 프로그래밍, 트리, 트리에서의 다이나믹 프로그래밍

설명

나 같은 경우에는 바로 안 풀리는 문제라고 할지라도 꽤나 오래 묵히면서 장고하는 스타일이다!

그렇다보니 이렇게 시도했지만 맞지 못한 문제에 대회 문항과 함께 거창한 시도를 했지만 풀지 못한 문제가 쌓이게 된다..

이것들을 치우기 위해 가끔 문제를 읽어보면서 곰씹는 편인데 오늘 드디어 이 글의 문제 해결법을 알게 되어 너무 기쁘다!

무려 첫 시도 이후 8개월이나 걸린 문제고 바로 직전 시도로부터 몇 번 건드려본 적은 있지만 마땅한 방안이 나지 않아서 해결하지 못했었다.

def pre_order_detail(graph_dict: dict, target_node: int = 1) -> list:

    result = [target_node]

    if len(graph_dict[target_node]) >= 1:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][0]):
            result.append(each_element)
        result.append(target_node)

    if len(graph_dict[target_node]) >= 2:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][1]):
            result.append(each_element)
        result.append(target_node)

    return result

원래는 위와 같은 재귀 함수의 형태로 전위 순회를 변형한 형태로 방문하는 노드를 찍어낸 뒤에 스택과 같은 자료 구조에 넣고 각 간선을 여차저차하는 방식을 생각했었다.

하지만 생각해보니 결과적으로 비교하는 대상을 같은 부모 노드로부터 나온 간선으로 한정 짓는다면 2개씩 비교한 값 중 큰 값을 꾸준히 상위 간선에 합산시키면서 처리할 경우 깔끔하게 계산이 가능하다는 것을 알 게 되었다!

나중에 풀고 분류를 보니 이런 문제의 유형이 트리 DP라고 한다. 확실히 DP의 그것과 많이 유사하다고 생각했다.

풀이 코드

# 이진 트리

import sys

input = sys.stdin.readline

tree_height = int(input())
node_number = pow(2, tree_height + 1)

edges = [0] + list(map(int, input().split()))
edge_sum = sum(edges)

now_start = node_number // 2 - 1
now_end = node_number - 1

while now_end:

    for i in range((now_end - now_start) // 2):

        child_edge = now_start + (2 * i)
        next_node = child_edge // 2

        edges[next_node] += max(edges[child_edge], edges[child_edge + 1])
        edge_sum += abs(edges[child_edge] - edges[child_edge + 1])

    now_end = now_start
    now_start = now_start // 2

print(edge_sum)

처음에 생각했던 방식보다 코드 길이도, 시간 복잡도도 깔끔해진 모습이다. 이렇게 놓고 보니 확실히 Bottom-Up 형태를 갖추고 있다.