이번에는 백준 9934번 완전 이진 트리 문제를 풀어보았습니다.
중위 순회 결과만 주어지고 각 레벨의 노드를 출력해야 하는 문제였습니다.
중위 순회의 특징을 생각해보면 항상 가운데 값이 현재 서브트리의 루트가 된다는 점을 이용할 수 있었습니다.
그래서 가운데 노드를 기준으로 왼쪽과 오른쪽 서브트리를 계속 나누는 DFS 방식으로 구현하였습니다.
문제 설명
깊이가 K인 완전 이진 트리의 중위 순회 결과가 주어집니다.
이 정보를 이용하여 트리를 복원한 뒤, 각 레벨에 존재하는 노드를 출력하는 문제입니다.
풀이 아이디어
중위 순회에서는 항상 현재 구간의 가운데 값이 루트가 됩니다.
처음에는 전체 구간의 가운데 값을 루트로 저장하였습니다.
이후 루트를 기준으로 왼쪽과 오른쪽 서브트리의 가운데 값을 찾아 다음 레벨에 저장하도록 구현하였습니다.
이를 재귀적으로 반복하면 각 레벨의 노드를 순서대로 구할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ret;
int inp_arr[1024];
int k;
void dfs(int size, int level, int idx) {
if(size == 0)
return;
int next_size = size/2;
int left = idx-next_size-1;
int right = idx+next_size+1;
ret[level+1].push_back(inp_arr[left]);
ret[level+1].push_back(inp_arr[right]);
dfs(next_size, level+1, left);
dfs(next_size, level+1, right);
}
int main() {
cin >> k;
int size = 1 << k;
size -= 1;
for (int i=0; i<size; i++) {
cin >> inp_arr[i];
}
ret.resize(k, vector<int>());
ret[0].push_back(inp_arr[size/2]);
dfs(size/2, 0, size/2);
for (int i=0; i<k; i++) {
size = ret[i].size();
for (int j=0; j<size; j++) {
cout << ret[i][j] << " ";
}
cout << '\n';
}
return 0;
}풀이 흐름
- 중위 순회 결과를 입력받습니다.
- 전체 구간의 가운데 값을 루트로 저장합니다.
- DFS를 이용하여 현재 구간의 왼쪽과 오른쪽 서브트리를 탐색합니다.
- 각 서브트리의 가운데 값을 다음 레벨에 저장합니다.
- 더 이상 탐색할 구간이 없으면 재귀를 종료합니다.
- 모든 레벨을 출력합니다.
구현 포인트
1. 가운데 값을 루트로 선택
중위 순회의 특징을 이용하여 전체 구간의 가운데 값을 루트로 저장하였습니다.
ret[0].push_back(inp_arr[size/2]);이후 이 값을 기준으로 왼쪽과 오른쪽 서브트리를 나누었습니다.
2. 현재 서브트리의 가운데 계산
현재 루트를 기준으로 다음 서브트리의 가운데 위치를 계산하였습니다.
int next_size = size/2;
int left = idx-next_size-1;
int right = idx+next_size+1;왼쪽과 오른쪽 서브트리의 루트 위치를 구하는 데 사용하였습니다.
3. 레벨별 저장
각 서브트리의 루트는 다음 레벨에 저장하였습니다.
ret[level+1].push_back(inp_arr[left]);
ret[level+1].push_back(inp_arr[right]);DFS가 진행될수록 레벨별 노드가 순서대로 저장됩니다.
4. 재귀적으로 서브트리 탐색
왼쪽과 오른쪽 서브트리를 계속 분할하며 탐색하였습니다.
dfs(next_size, level+1, left);
dfs(next_size, level+1, right);현재 서브트리의 가운데를 계속 찾는 방식으로 트리를 복원하였습니다.
5. 탐색 종료
더 이상 분할할 노드가 없는 경우 재귀를 종료하였습니다.
if(size == 0)
return;리프 노드까지 모두 탐색하면 DFS가 종료됩니다.
