Sign in Subscribe
PS

[PS] BOJ 2263 / 트리의 순회

Minjun Kim

• 3 min read
[PS] BOJ 2263 / 트리의 순회
문제 링크: https://www.acmicpc.net/problem/2263
Thumbnail: Photo by Antoine PERIER (Unsplash)

풀이

​트리의 inorder 순회 결과와 postorder 순회 결과가 주어질 때, preorder 순회의 결과를 구하는 문제입니다.

트리의 순회?

트리를 순회하는 방식 4가지를 먼저 이해해야 합니다.

  • preorder (전위 순회)
    • 루트 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
  • inorder (중위 순회)
    • 왼쪽 자식 노드 -> 루트 노드 -> 오른쪽 자식 노드
  • postorder (후위 순회)
    • 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 루트 노드
  • levelorder (층별 순회)
    • 각 노드를 깊이(level) 순서대로 출력합니다.

이 문제는 inorder와 postorder 순회의 결과를 토대로 preorder의 결과를 출력하는 문제입니다.

트리 재구성

postorder의 순회 순서를 보면, 항상 루트 노드를 마지막으로 방문함을 알 수 있습니다. 따라서, postorder의 순회 결과의 마지막 노드는 해당 트리의 루트 노드입니다.

postorder에서 찾은 루트 노드를 inorder 순회 결과에서 찾은 뒤, 그 앞과 뒤를 쪼개면 각각 왼쪽 서브트리, 오른쪽 서브트리의 inorder 순회 결과가 됩니다.

두 순회 결과를 통해, 왼쪽과 오른쪽의 두 서브트리를 쪼갤 수 있습니다. 이 각각의 서브트리에 대해서도 동일한 과정을 반복해 트리를 재구성할 수 있습니다.

이 문제에서는 전위 순회 결과를 출력하면 되므로, 다음 순으로 진행하면 됩니다.

  1. 루트 노드 출력하기
  2. 왼쪽 서브트리에 대해 재귀
  3. 오른쪽 서브트리에 대해 재귀

문제를 부분 문제로 나누어 푼 뒤 결과를 합치는 방식, 이는 분할 정복(Divide and Conquer) 알고리즘 기법입니다.

서브트리를 함수의 인자로 넘길 때 주의할 것

파이썬에는 리스트를 슬라이싱 할 수 있습니다. 하지만, 슬라이싱의 경우 복제된 새 객체를 만들게 되므로 메모리 낭비가 심해집니다.

따라서, 이 문제에서는 슬라이싱 대신에 서브트리에 해당하는 시작 밑 끝 인덱스를 재귀호출 시 매개변수로 전달하는게 효율적입니다.

전체 코드

from sys import setrecursionlimit
setrecursionlimit(10**5)

input = open(0).readline
N = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

def build_tree(in_start, in_end, post_start, post_end):
    """중위 순회와 후위 순외 정보로부터 트리를 재구성해 전위 순회 결과를 출력한다.
    Arguments:
        in_start {int} -- 중위 순회의 시작 인덱스   (포함됨)
        in_end {int} -- 중위 순회의 끝 인덱스       (포함되지 않음)
        post_start {int} -- 후위 순회의 시작 인덱스 (포함됨)
        post_end {int} -- 후위 순회의 끝 인덱스     (포함되지 않음)
    """
    if post_start < post_end and in_start < in_end:
        root = post_order[post_end - 1]
        subtree_root = in_order.index(root, in_start, in_end + 1)
        print(root, end=" ") # 전위이므로 탐색 전에 출력
        # 중위 순회에서 찾은 루트 노드의 인덱스는 후위 순회에서의 루트 노드의 인덱스와 동일하지 않다. 상대적인 위치를 계산해줘야 한다.
        build_tree(in_start, subtree_root, post_start, post_start + (subtree_root - in_start))
        build_tree(subtree_root + 1, in_end, post_start + (subtree_root - in_start), post_end - 1)

build_tree(0, N, 0, N)

solution.py