백준 4256 | 트리 (트리, 재귀, 분할정복)

문제 출처 : https://www.acmicpc.net/problem/4256

문제

• 루트 노드가 유일한 이진 트리가 있다.
• 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다.
• 자식이 없는 노드를 리프 노드라고 부른다.
• BT(이진 트리, Binary Tree)의 모든 노드를 탐색하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 로 총 세 가지가 있다.
• BT를 전위 순회, 중위 순회한 결과가 주어지면, 두 순회한 겨과를 가지고 다시 BT를 만들 수 있다.
• BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

문제 접근 방법

아이디어

1. 전위 순회의 결과를 통해 첫번째 인덱스가 루트 노드인 것을 알 수 있다.
2. 루트 노드가 중위 순회에서 몇 번째 노드인지 찾아서 왼쪽 서브 트리인 노드를과 오른쪽 서브 트리인 노드들을 찾는다.
3. 후위 순회에 맞게 재귀적으로 (왼쪽) (오른쪽) (루트) 의 순으로 탐색을 진행한다.
4. 리스트 슬라이싱을 통해 왼쪽 서브 트리와 오른쪽 서브트리에 대해 재귀적으로 후위 순위의 결과를 찾는다.

전위 순회 vs 중위 순회 vs 후위 순회

• 전위, 중위, 후위 순휘는 이진트리를 탐색할 때 루트노드들 언제 탐색하는지에 따라 다르다.
• 왼쪽 서브 트리는 무조건 오른쪽 서브 트리보다 먼저 탐색을 진행하는데 루트 노드를 어디에 넣을 것인가?
  라고 생각하면 외우기 쉽다.
• 전위 순회 : 루트 노드를 왼쪽 서브 트리보다 먼저 탐색
  • (루트 노드) (왼쪽 서브 트리) (오른쪽 서브 트리)
• 중위 순회 : 왼쪽 서브 트리 탐색 후 오른쪽 서브 트리를 탐색하기 전에 루트 노드를 탐색
  • (왼쪽 서브 트리) (루트 노드) (오른쪽 서브 트리)
• 후위 순회 : 왼쪽 서브 트리 탐색, 오른쪽 서브 트리 탐색 후 루트 노드 탐색
  • (왼쪽 서브 트리) (오른쪽 서브 트리) (루트 노드)

구체적인 구현 과정

• 예제 입력에서 8개의 노드가 있고

  • 전위 순회 : 3 6 5 4 8 7 1 2
  • 중위 순회 : 5 6 8 4 3 1 2 7 가 있을 때,

• 우리는 전위 순회가 (루트 노드) -> (왼쪽 서브 트리) -> (오른쪽 서브 트리) 순으로 탐색하는 것을 알기 때문에

  • 전위 순회의 결과의 첫번째 인덱스인 3 이 루트 노드인 것을 알고 있다.

• 중위 순회는 (왼쪽 서브 트리)->(루트 노트)->(오른쪽 서브 트리) 으로 순회하므로 루트노드인 3 의 위치를 알면

  • 왼쪽 서브 트리 : 0 ~ (루트노드의 인덱스 - 1) 의 인덱스
  • 오른쪽 서브 트리 : (루트노드의 인덱스 + 1) ~ 끝 의 인덱스

• 임을 알 수 있다.

• 이렇게 찾은 각각의 왼쪽 오른쪽 서브트리에 대해 더 이상 쪼갤 수 없을 때까지

  • 재귀적으로 각각의 왼쪽 서브트리의 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리를 찾아나가면서
  • 후위 순위의 순서 (왼쪽 서브 트리)->(오른쪽 서브 트리)->(루트 노드) 에 맞게 이어나간다.

• 설명이 부족한 것 같지만 코드와 함께 본다면 더 이해가 빨리 될 것 같다.

코드

import sys

input = sys.stdin.readline

# 테스트 케이스의 개수
cases = int(input())

def get_postorder(preorder, inorder):
    # 전위 순위의 첫인덱스는 루트 노드
    root = preorder[0]
    # 중위 순위에서 루트 노드는 가운데 있으므로
    # 루트 노드의 인덱스를 통해 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있다. 
    root_idx = inorder.index(root)
    left = inorder[:root_idx]
    right = inorder[root_idx + 1:]

    post_left, post_right = [], []

    # 후위 순회의 순서에 맞게 (왼쪽)(오른쪽)(루트) 의 순서로 답을 찾아나간다
    # 이때 왼쪽, 오른쪽 서브트리에 대해 재귀적으로 각각의 루트, 왼쪽, 오른쪽 서브트리를 찾아서 후위 순회로 바꾼다.
    if left:
        post_left = get_postorder(preorder[1:root_idx + 1], inorder[:root_idx])
    if right:
        post_right = get_postorder(preorder[root_idx + 1:], inorder[root_idx + 1:])

    return post_left + post_right + [root]

for _ in range(cases):
    n = int(input())
    # preorder : 전위 순위의 결과, inorder : 중위 순위의 결과
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))

    # post_list : 후위 순위의 결과 값 저장
    post_list = get_postorder(preorder, inorder)
    print(*post_list)