BOJ 4256 트리 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

이진 트리

모든 노드는 최대 2개의 자식 노드 가질 수 있으며, 왼쪽 자식이 순서가 먼저임.

노드 n개로 이뤄진 이진 트리를 BT라 하자.

BT의 노드는 1부터 n까지 유일한 번호 매겨짐.

BT의 루트는 3번 노드임. 이때 1번 노드는 오른쪽 자식만 가지고 있음.

4,7은 왼쪽 노드만, 3과 6은 왼쪽과 오른쪽 자식 모두 가짐.

나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라 부름

BT의 모든 노드를 순회하는 방법

전위 순회, 중위 순회, 후위 순회로 총 3가지.

위 3가지는 아래 C 스타일의 의사코드로 나와있음.

BT의 노드 v에 대해 v.left: 왼쪽 자식, v.right: 오른쪽 자식.

v가 왼쪽 자식이없으면 v.left는 ∅과 같고 오른쪽 자식이 없으면 v.right는 ∅과 같음.

BT를 전위 순회, 중위 순회한 결과가 주어짐.

즉 위의 함수중 preorder, inorder를 호출해 만든 리스트가 주어짐.

두 순회한 결과를 가지고 다시 BT를 만들 수 있음.

BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램 작성하세요.

위의 그림을 전위 순회: 3, 6, 5, 4, 8, 7, 1, 2/ 중위 순회: 5, 6, 8, 4, 3, 1, 2, 7

위를 이용해 후위 순회하면: 5, 8, 4, 6, 2, 1, 7, 3.

• 입력

  첫째 줄: 테스트 케이스 개수 T

  각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어짐.(1≤n≤1000)

  BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져있음.

  다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어짐.

  항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어짐.

• 출력

  각 테스트 케이스마다 후위 순회한 결과 출력.

두 번째 단계 (문제 핵심 파악)

중요한 포인트

• 전위 순회의 첫번째 요소는 root노드이다.
• 중위 순회에서 root노드 기준으로 왼쪽 요소들은 왼쪽 서브트리이며 오른쪽 요소들은 오른쪽 서브트리이다.

코드 작성

import sys

input = sys.stdin.readline


# 후위순회
def make_post_order(pre, in_):
    # 재귀 종료 조건: 트리가 되지 못하는 경우
    if len(pre) == 0:
        return
    elif len(pre) == 1:
        print(pre[0], end=' ')
        return
    elif len(pre) == 2:
        print(pre[1], pre[0], end=' ')
        return

    root = pre[0]  # root 노드는 전위 순회의 첫번째 요소
    mid_idx = in_.index(root)  # 중위 순회에서 루트 노드는 왼쪽 서브 트리와 오른쪽 서브 트리른 나누는 기준에 위치

    # 전위 순회
    pre_left_sub_tree = pre[1:mid_idx+1]  # 왼쪽 서브 트리
    pre_right_sub_tree = pre[mid_idx + 1:]  # 오른쪽 서브 트리

    # 중위 순회
    in_left_sub_tree = in_[:mid_idx]  # 왼쪽 서브트리
    in_right_sub_tree = in_[mid_idx + 1:]  # 오른쪽 서브트리

    # 재귀
    make_post_order(pre_left_sub_tree, in_left_sub_tree)
    make_post_order(pre_right_sub_tree, in_right_sub_tree)

    # 출력
    print(root, end=' ')


# 입력
t = int(input())  # test case
for _ in range(t):
    n = int(input())  # 노드 수
    pre_order = list(map(int, input().split()))
    in_order = list(map(int, input().split()))

    make_post_order(pre_order, in_order)
    print()

느낀점

트리 + 재귀 라서 골드2 난이도인 것 같다.

트리 관련해서 문제를 몇개 풀어봤는데, 이 문제는 root노드를 찾아 왼쪽 서브 트리와 오른쪽 서브트리로 나누고 재귀의 조건을 거는게 중요한 문제였다.