[백준 2263번] 트리의 순회 (C++, Python3)
https://www.acmicpc.net/problem/2263
2263번: 트리의 순회
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
이번 포스트에서는 백준 알고리즘 문제인 트리의 순회를 포스트하도록 하겠습니다.
해당 문제는 solved.ac 기준 골드 1에 위치한 문제입니다.
먼저 문제입니다.
정점 수 N이 입력으로 주어지고, N개의 정점을 갖는 이진 트리의 중위 순회 결과와 후위 순회 결과를 입력받습니다.
출력으로 해당 이진 트리의 전위 순회를 출력하는 문제입니다.
해당 문제를 해결하기 위해서 먼저 중위순회와 후위순회, 전위 순회에 대한 이해가 필요합니다.
EX)
중위 순회 결과 : 8 4 9 2 5 1 6 3 7
후위 순회 결과 : 8 9 4 5 2 6 7 3 1
이렇게 출력될 때, 후위 순회는 순서가 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 노드 순으로 진행됩니다.
따라서, 후위 순회의 마지막은 항상 루트노드입니다.
그러므로 후위 순회의 마지막 값(루트 노드)이 중위 순회 상에서 위치한 인덱스를 기준으로 분할합니다.
중위순회는 왼쪽 서브트리 - 루트 노드 - 오른쪽 서브트리 순으로 진행되므로, 루트 노드를 기준으로 분할했기 때문에
왼쪽 서브트리에 있는 노드 개수만큼 후위 순회 상에서 탐색할 범위를 정합니다. (결국 왼쪽 서브트리의 노드 수는 중위 순회나 후위 순회나 같기 때문에 노드 개수로 잘라서 탐색)
그리고 다시 루트노드를 찾고 분할하는 방식으로 전위 순회를 찾습니다.
전위순회는 루트 노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 진행되기 때문에 루트를 찾고 출력하고 다 찾게 되면 왼쪽 서브트리를 접근하는 순서로 진행하면됩니다.
다음은 C++ 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
using namespace std;
int inOrder[100001];
int postOrder[100001];
int tmp[100001];
void preOrder(int inFirst, int inEnd, int postFirst, int postEnd) {
if(inFirst > inEnd || postFirst > postEnd) return;
int root = postOrder[postEnd];
int idx = tmp[root];
int leftLength = idx - inFirst;
cout << root << " ";
preOrder(inFirst, idx - 1, postFirst, postFirst + leftLength - 1);
preOrder(idx + 1, inEnd, postFirst + leftLength, postEnd - 1);
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> inOrder[i];
for(int i = 0; i < n; i++)
cin >> postOrder[i];
for(int i = 0; i < n; i++)
tmp[inOrder[i]] = i;
preOrder(0, n - 1, 0, n - 1);
return 0;
}
|
cs |
다음은 Python 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import sys
sys.setrecursionlimit(10**6)
n = int(input())
inOrder = list(map(int, input().split()))
postOrder = list(map(int, input().split()))
tmp = [0] * 100001
for i in range(n) :
tmp[inOrder[i]] = i
def preOrder(inFirst, inEnd, postFirst, postEnd) :
if inFirst > inEnd or postFirst > postEnd :
return
root = postOrder[postEnd]
idx = tmp[root]
leftLength = idx - inFirst
print(root, end=" ")
preOrder(inFirst, idx - 1, postFirst, postFirst + leftLength - 1)
preOrder(idx + 1, inEnd, postFirst + leftLength, postEnd - 1)
preOrder(0, n - 1, 0, n - 1)
|
cs |
파이썬에서는 백준의 재귀함수 호출이 제한되어 있으므로 sys.setrecursionlimit을 설정하여 재귀함수 제한을 늘려줍니다.
해당 문제는 후위순회와 중위순회, 전위순회의 특징과 이를 분할정복으로 연계해야하는 점 때문에 난이도가 꽤 높다고 생각합니다.
다음 포스트에서 또 다른 백준 알고리즘 문제로 포스트하도록 하겠습니다. 감사합니다.