알고리즘 유형 : 트리(순회)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/2263
소스 코드(파이썬)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
# position[a] = b 는 a 값이 inorder의
# b번째 인덱스에 존재한다는 뜻이다
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
# 후위 순회의 마지막 노드는 트리의 루트 노드
parent = postorder[post_end]
print(parent, end=" ")
# 중위 순회값에서 루트 노드의 위치(인덱스)
in_parent_idx = position[parent]
# 중위 순회값에서 루트 노드 위치 왼쪽편은 왼쪽 서브트리의 중위 순회값임
# 오른쪽도 마찬가지
left_len = in_parent_idx - in_start
right_len = in_end - in_parent_idx
# 중위 순회값에서 구한 왼쪽 서브트리, 오른쪽 서브트리의 크기 값을
# 활용한다. 후위 순회값에서 왼쪽에서 left_len 만큼이 왼쪽 서브트리,
# 오른쪽에서 젤 오른쪽 노드 하나를 제외한 right_len 만큼이 오른쪽
# 서브트리 후위 순회값임
# 루트 노드를 print 하고, 왼쪽 서브트리와 오른쪽 서브트리의
# 전위 순회를 구한다는 점에서 분할 정복을 적용할 수 있다.
pre_left = preorder(in_start, in_start + left_len - 1,
post_start, post_start + left_len - 1)
pre_right = preorder(in_end - right_len + 1, in_end,
post_end - right_len, post_end - 1)
return
preorder(0, n-1, 0, n-1)풀이 요약
-
중위 순회와 후위 순회를 이용하여 전위 순회를 구할 수 있다.
후위 순회 이용 : 어떤 트리에 대해, 후위 순회의 마지막 노드는 루트 노드이다. 이는 곧 전위 순회의 가장 첫 번째 노드가 된다.
ex) 후위 순회 : 3 4 8 1 9 5 2 7 6 이면, 6이 전위 순회의 첫 번째 노드가 된다.
중위 순회 이용에 앞서 한 가지를 더 알아보자.
-
결론부터 말하면 분할 정복 개념을 적용하여 풀 것이다.
후위 순회의 성질을 이용하여 전위 순회의 첫 번째 노드를 찾았다. 그 후, 루트 노드의 왼쪽 서브트리, 오른쪽 서브트리의 전위 순회를 각각 알아내어 이어붙여주면 전체 트리에 대한 전위 순회가 된다.
이 때,
서브트리의 전위 순회를 구하는 과정 또한서브트리의 후위 순회의 마지막 노드를서브트리의 전위순회의 첫 번째 노드로 삼는다.똑같은 과정이 점점 범위가 좁아지면서 계속 반복된다. 그리고 나뉜 문제를 해결하여 합쳐서 전체 문제를 구하므로, 분할 정복을 적용할 수 있는 구조이다.
ex) 중위 순회 : 4 3 9 8 1 6 2 5 7 이고, 후위 순회 : 3 4 8 1 9 5 2 7 6 일 때, 전위 순회의 첫 번째 노드는 6이고, 이 제 그 뒤에 루트 노드 6의 왼쪽 서브트리의 전위 순회, 오른쪽 서브트리의 전위 순회를 각각 구한 뒤 이어붙여줄거임.
왼쪽 서브트리의 전위 순회를 구하기 위해서는, 왼쪽 서브트리에 해당하는 중위 순회와 후위 순회가 필요함.
중위 순회에서 루트 노드 6 기준 왼쪽의 노드들은 왼쪽 서브트리의 중위 순회를 의미함. 즉 4 3 9 8 1
이 때, 왼쪽 서브트리 중위 순회 길이가 5임. 즉, 왼쪽 서브트리의 후위 순회 길이도 5여야하고, 후위 순회는 왼쪽-오른쪽-부모노드 이기 때문에, 맨 왼쪽부터 5개의 노드, 3 4 8 1 9 가 왼쪽 서브트리에 대한 후위 순회이다.
-
위의 ex에서 본대로 왼쪽 서브트리의 중위 순회와 후위 순회를 구하고나면, 똑같은 작업을 반복하면 된다. 후위 순회 마지막 노드를 전위 순회에 넣고, 다시 왼쪽과 오른쪽 서브트리에 같은 작업을 반복한다.
이는 재귀 함수를 활용하여 구현한다.
- 상세한 구현은 코드의 주석을 참고하자.
배운 점, 어려웠던 점
- 트리 순회의 성질과 관계를 더 잘 익힐 수 있어 유익한 문제였다.
