[#5639] 이진 검색 트리

RookieAND·2022년 6월 15일

백준 이진탐색 재귀 코테 트리

BaekJoon

목록 보기

14/42

❓ Question

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

📖 Before Start

트리를 어떤 방식으로 탐색하느냐 에 따라 검색 과정이 달라질 수 있다.

이번 문제는 일전에 트리 자료구조를 학습하면서 배웠던 전위, 후위 탐색과 관련된 문제였다.
이전까지는 단순히 탐색 과정이 다르다는 것만 알았는데, 이번 문제는 이전 탐색을 통해 나온
결과를 이용하여 새로운 탐색 과정 결과를 유도해야 하는... 상당히 혼란스러운 문제였다.

✒️ Design Algorithm

전위 탐색 결과로부터 트리를 도출하고, 이를 토대로 후위 탐색을 진행한다.

전위 탐색 결과는 결국 트리를 이루는 노드들이므로, 이를 하나의 List로 묶어 트리를 재구성하였다.
그 후 구성된 트리를 후위 탐색하여 나온 결과를 그대로 돌려주면 된다 생각하고, 코드를 작성했다.

먼저 전위 탐색의 결과를 이용하여 기존의 트리를 재구성해보자.

전위 탐색의 가장 첫 번째 결과 값은 해당 트리의 루트 노드 이므로 이를 저장한다.
그 후 전위 탐색의 결과를 입력 받고, 이진 탐색을 통해 트리에 노드를 추가한다.
마지막으로 완성된 트리를 대상으로 후위 탐색을 진행하여 결과를 출력시킨다.

💻 Making Own Code

❌ Wrong Code

import sys
sys.setrecursionlimit(10 ** 6)

class Node:
    def __init__(self, data, l_node, r_node):
        self.data = data
        self.left = l_node
        self.right = r_node

read = sys.stdin.readline
tree = {}
root = Node(int(read()), None, None)
tree[root] = root

def insert_node(node, p_node):
    if p_node.data > node.data:
        if not p_node.left:
            p_node.left = node
            return
        insert_node(node, p_node.left)
    if p_node.data < node.data:
        if not p_node.right:
            p_node.right = node
            return
        insert_node(node, p_node.right)


def post_order(node):
    if node.left != None:
        post_order(node.left)
    if node.right != None:
        post_order(node.right)
    print(node.data)


while True:
    try:
        node = Node(int(read()), None, None)
        insert_node(node, root)
    except:
        break
post_order(root)

풀이 자체는 틀리지 않았다. 하지만 메모리 초과가 오늘도 발목을 잡았다.

설계 과정에서 틀린 점은 없었으나, 트리를 재구성하는 과정에서 많은 메모리가 필요하였다.
재귀 함수로 트리의 각 노드들을 순회하면서 새로운 노드를 추가하는 과정이 문제라 생각했다.

따라서 이 문제는 올바른 접근법을 알아내기 위해 결국 외부 자료의 힘을 빌릴 수밖에 없었다.
전위 탐색으로 얻은 결과는 [루트 노드 - 좌측 서브 트리 - 우측 서브 트리] 순으로 나열된다.
이를 통해 다음과 같은 이진 탐색 으로 후위 탐색을 구현할 수 있다.

전위 탐색으로 얻은 결과를 순차적으로 입력 받아 하나의 List 에 저장한다.
그런 뒤, 해당 List 의 0번째 index 에 저장된 값을 루트 노드 로 설정한다.
이후 다음 인덱스부터 탐색을 진행하여, 루트 노드보다 값이 커지는 인덱스를 구한다.
시작점부터 분기점 전까지의 범위를 좌측, 이후 끝까지의 범위가 우측 서브 트리이다.
각의 범위에 대한 탐색을 재귀 함수로 시행하고, 최종적으로 루트 노드 를 출력시킨다.

✅ Correct Code

import sys
sys.setrecursionlimit(10 ** 5)

# 이진 탐색을 통해 후위 탐색 결과를 출력시키는 함수.
def post_order(start, end):
    if start > end:
        return
    # 전위 탐색은 루트 노드가 맨 앞에 위치하므로, 이를 root로 설정.
    root = pre_order[start]
    index = start + 1
    # 루트 노드 바로 다음 인덱스부터 끝까지 이진 탐색 시작.
    # root 값보다 더 큰 값이 나오기 전까지 index 범위 증가.
    while index <= end:
        if pre_order[index] > root:
            break
        index += 1
    # 시작 범위부터 root 값보다 작은 범위까지 후위 탐색
    post_order(start + 1, index - 1)
    # root 값보다 큰 범위에서 끝 범위까지 후위 탐색.
    post_order(index, end)
    # 탐색을 모두 마쳤다면, 루트 노드 출력
    print(root)

# try-except 로 입력이 종료될때까지 전위 탐색 결과를 받음.
pre_order = []
while True:
    try:
        pre_order.append(int(sys.stdin.readline()))
    except:
        break

post_order(0, len(pre_order) - 1)