반응형
문제 링크: www.acmicpc.net/problem/4256
4256번: 트리
문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n��
www.acmicpc.net
<문제 풀이> DFS(깊이 우선 탐색), 트리
전위 순회 결과 3 6 5 4 8 7 1 2
중위 순회 결과 5 6 8 4 3 1 2 7
중위 순회 결과를 통해서 각 노드의 순서를 알 수 있고, 왼쪽 서브 트리와 오른쪽 서브 트리에 어떤 노드가 존재하는지 알 수 있습니다.
그리고 전위 순회 결과를 통해 규칙을 찾아볼 수 있는데, 크기가 n인 배열에 전위 순회 결과가 차례로 저장돼 있다고 했을 때 인덱스 + 1을 하면 왼쪽 서브 트리의 루트를 가리키게 할 수 있습니다.
예를 들어 arr [] = {3 ,6, 5, 4, 8, 7, 1, 2]인 배열이 있습니다. 이때
root == 3, index = 0 되고, 왼쪽 서브 트리로 이동하면
root == 6, index = 1 이 됩니다.
그리고 오른쪽 서브트리로 이동하는 방법은 왼쪽 서브 트리의 크기 + 1 만큼 인덱스를 더해주면 됩니다.
root == 3, index = 0
root == 7, index = 0 + 4 + 1 == 5
<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
|
#include <iostream>
#include <vector>
using namespace std;
int preorder[1001];
int inorder[1001];
void solution(int root, int s, int e){
for(int i = s ; i < e; i++){
if(inorder[i] == preorder[root]){
solution(root + 1, s, i); // left sub tree
solution(root + i + 1 - s, i + 1, e); // right sub tree
cout<<preorder[root]<<" ";
}
}
}
int main(void) {
int test_case;
cin>>test_case;
while(test_case--){
int n ; cin>>n;
for(int i=0; i<n; i++){
cin >> preorder[i];
}
for(int i=0; i<n; i++){
cin >> inorder[i];
}
solution(0, 0, n);
cout<<'\n';
}
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 10871번] X보다 작은 수 (0) | 2021.10.02 |
|---|---|
| [백준 1197번] 최소 스패닝 트리 (0) | 2020.07.26 |
| [백준 10974번] 모든 순열 (0) | 2020.07.05 |
| [백준 2623번] 음악프로그램 (0) | 2020.04.11 |
| [백준 2252번] 줄 세우기 (0) | 2020.04.03 |
