[백준/BOJ] 9934번 완전 이진 트리

https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

중위 탐색의 결과를 완전 이진 트리로 바꿔야 하는 문제다.

특정 depth까지 left와 right을 설정해 루트 노드를 탐색하는 방법을 반복하면서 문제를 해결하는데, 이분 탐색을 재귀로 구현하는 것과 비슷하다.

 

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)
using namespace std;
typedef long long ll;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer, L, R, _x1, _x2, _y1, _y2, flag;
int a[2000], visited[2000];
vector<int> res[10];

void DFS(int depth, int left, int right) {
	if(depth >= n) return;
	int root = (left + right) / 2;
	if((root >= 0 && root < k) && !visited[root]) {
		visited[root] = 1;
		res[depth].push_back(a[root]);
		DFS(depth + 1, left, root - 1);
		DFS(depth + 1, root + 1, right);	
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	k = (1 << n) - 1;
	for(int i = 0; i < k; i++) {
		cin >> a[i];
	}
    
	if(n == 1) {
		cout << a[0];
		return 0;
	}
    
	DFS(0, 0, k - 1);
    
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < res[i].size(); j++) {
			cout << res[i][j] << " ";
		}
		cout << "\n";
	}
}