[#2263] 트리의 순회

RookieAND·2022년 6월 16일

백준 분할정복 재귀 코테 트리

BaekJoon

목록 보기

15/42

❓ Question

https://www.acmicpc.net/problem/5639

📖 Before Start

각기 다른 트리의 탐색 결과 를 토대로 다른 탐색을 유추하는 문제였다.

이번 문제는 일전에 트리 자료구조를 학습하면서 배웠던 중위, 후위 탐색과 관련된 문제였다.
분명 저번 문제도 트리 탐색과 관련된 문제를 풀었기에 이번에도 쉽게 풀겠다고 생각했지만...
정말 트리 문제는 알다가도 모르겠다. 문제를 읽으면서도 도통 감이 잡히지 않았다.

✒️ Design Algorithm

후위 탐색 결과의 마지막은 루트 노드라는 걸 떠올리고, 풀이를 구상하였다.

후위 탐색을 통해 나온 결과 중, 가장 마지막에 위치한 값이 트리의 루트 노드 이다.
그리고 중위 탐색 의 경우, 루트 노드를 기준으로 트리의 좌우 영역이 나뉘어지며
이를 통해 좌측 서브 트리와 우측 서브 트리를 구할 수 있음을 고민 끝에 알아내었다.

분할 정복을 사용하여, 두 서브 트리에 대한 전위 탐색을 재귀 함수로 구현!

후위 탐색으로 루트 노드를 얻고, 중위 탐색에서 몇 번째 인덱스 에 위치했는지를 구한다.
그 후 인덱스 를 기준으로 좌측 서브 트리 와 우측 서브 트리 영역을 구분 짓는다.
전위 탐색의 순서에 따라, 루트 노드를 출력시키고 두 영역에 대한 재귀 함수를 시행한다.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline
N = int(read())
in_orders = list(map(int, read().split()))
post_orders = list(map(int, read().split()))

def pre_order(in_order, post_order):
    start, end = 0, len(in_order) - 1
    if start > end:
        return
    root = post_order[end]
    index = start
    while index <= end:
        if in_order[index] == root:
            break
        index += 1
    print(root, end=' ')
    # 좌측 서브 노드와 우측 서브 노드에 해당되는 영역을 주고, 재귀 함수 실행
    pre_order(in_order[start:index], post_order[start:index])
    pre_order(in_order[index+1:end+1], post_order[index:end])

pre_order(in_orders, post_orders)

List 자체를 계속해서 할당시키다 보니, 메모리 초과가 발생했다.

설계 과정에서 틀린 점은 없었으나, 영역을 분할하는 과정에서 많은 메모리가 필요하였다.

따라서 다음에는 탐색의 시작과 끝 영역을 매개변수로 주어 함수를 구성했으나, 실패했다.
루트 노드의 인덱스를 기준으로 좌우 범위를 나누려는 시도를 안해본 것은 아니었으나,
우측 서브 트리의 범위를 잘못 판별하여 재귀를 탈출할 수 없는 문제에 직면하였다.

이 문제도 정말 2시간 동안 고민하면서 포기하지 않으려 했지만... 결국 다른 풀이를 보았다.
정답 풀이 방식은 어느 정도 비슷했으나, 각 서브 노드의 수량 을 기준으로 범위를 나누었다.

✅ Correct Code

import sys
sys.setrecursionlimit(10 ** 5)

read = sys.stdin.readline
N = int(read())
in_order = list(map(int, read().split()))
post_order = list(map(int, read().split()))

# 중위 탐색 결과들이 몇 번째 인덱스에 있는지를 저장하는 List
position = [0] * (N + 1)
for i in range(N):
    position[in_order[i]] = i


def pre_order(in_start, in_end, post_start, post_end):
    if in_start > in_end or post_start > post_end:
        return
    root = post_order[post_end]
    print(root, end=' ')
    # 좌측 서브 트리와 우측 서브 트리의 노드 수량을 계산
    left = position[root] - in_start
    right = in_end - position[root]

    # 좌측 서브 노드와 우측 서브 노드에 해당되는 영역을 주고, 재귀 함수 실행
    pre_order(in_start, in_start + left - 1, post_start, post_start + left - 1)
    pre_order(in_end - right + 1, in_end, post_end - right, post_end-1)


pre_order(0, N-1, 0, N-1)