[Python] BOJ 2263 : 트리의 순회

👉 백준 2263: 트리의 순회

✔️ 문제 풀이 포인트

• 중위 순회와 후위 순회의 특징을 캐치하여서 트리를 구성해도 되고,
  바로 전위 순회만 출력해도 된다.

1) 전위 순회는 가장 먼저 루트가 출력되고, 그다음 왼쪽 서브트리로 넘어가 서브트리의 루트를 출력하고 다시 왼쪽으로 넘어가는 것을 반복한다. 이후 왼쪽 서브트리 순회를 마치면 오른쪽으로 넘어감을 먼저 생각하고 있어야한다. 즉 BOJ 1991 문제에서 보았던 것 처럼 이 문제에서도 전위 순회는 아래 방식으로 문제 설계를 하면 된다.

print(루트)
left 서브트리 재귀
right 서브트리 재귀

2) 중위 순회는 루트가 순회 중간에 나오고 루트를 중심으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리이다.

3) 후위 순회는 루트노드가 가장 마지막에 나타나고 그 전은 오른쪽 서브트리의 루트이다.

중위 순회와 후위 순회의 특징을 이용하여 추적하면 트리를 구성할 수 있다.

position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i

• 먼저 후위 순회의 끝값이 중위 순회의 어디 인덱스에 위치한지 확인을 위해 중위 순회의 값들의 인덱스값을 저장한다.

def preorder(in_start, in_end, post_start, post_end):
	if (in_start > in_end) or (post_start > post_end): return

• 이분 탐색이나 분할 정복과 동일하게 start와 end가 만나 수렴하는 조건을 재귀 종료 조건으로 설정한다.

parents = postorder[post_end]
print(parents, end=" ")

• 후위 순회는 루트노드가 가장 마지막에 나타난다. 이를 이용해서, 전위 순회는 처음 루트가 가장 먼저 나오고 그다음 왼쪽으로 넘어가는 방식이기 때문에 후위 순회의 가장 마지막 값(루트)를 출력한다.

left = position[parents] - in_start
right = in_end - position[parents]

preorder(in_start, in_start+left-1, post_start, post_start+left-1)
preorder(in_end-right+1, in_end, post_end-right, post_end-1)

• 그리고 left와 right를 구하여 범위를 좁히고, 좁힌 범위로 왼쪽 - 오른쪽 각각 서브트리로 재귀방식으로 파고들어서 전위 순회를 추적한다.

✏️ 전체 코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# 분할 정복 방식으로 전위 순회를 찾음
def preorder(in_start, in_end, post_start, post_end):
    # 재귀 종료 조건 (수렴)
    if(in_start > in_end) or (post_start > post_end):
        return

    # 후위 순회 결과의 끝이 (서브)트리의 루트임을 이용
    parents = postorder[post_end]
    print(parents, end=" ")

    # 중위 순회에서 루트의 좌 우로 자식들이 갈라지는 것을 이용하여 left, right를 선언
    left = position[parents] - in_start
    right = in_end - position[parents]

    # left, right로 나눠 분할 정복 방식으로 트리를 추적하여 전위 순회를 찾아냄
    preorder(in_start, in_start+left-1, post_start, post_start+left-1) # 쪽 서브트리
    preorder(in_end-right+1, in_end, post_end-right, post_end-1) # 오른쪽 서브트리

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

# 후위 순회의 끝값이 중위 순회의 어디 인덱스에 위치한지 확인을 위해
# 중위 순회의 값들의 인덱스값을 저장
position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i

# 중위 순회, 후위 순회 모두 0부터 n-1 (전체 범위)값을 주고 전위 순회를 구함
preorder(0, n-1, 0, n-1)