[C++] 백준 9934번 완전 이진 트리

문제 링크

9934번: 완전 이진 트리

문제 요약

완전 이진 트리에 대해서 문제에서 제시된 규칙을 따르는 방문 순서가 주어진다. 이 방문 순서를 참고하여 트리에서 깊이별로 원소를 출력해야 한다.

접근 방법

테스트케이스와 문제의 그림을 보면, 구간의 중간의 원소가 서브트리의 루트임을 알 수 있습니다.

1 6 4 3 5 2 7

이 입력에서 루트 노드는 가운데의 3번 노드가 됩니다. 3번 노드를 기준으로 왼쪽과 오른쪽은 각각 하나의 서브트리를 이룹니다.

1 6 4

3번 노드의 왼쪽 서브트리를 보면 마찬가지로 가운데에 있는 6번 노드가 루트가 됩니다.

5 2 7

3번 노드의 오른쪽 서브트리 역시 가운데의 2번 노드가 루트가 됩니다.

이를 이용해서 구간을 쪼개면서 재귀호출을 하는 방식으로 각각의 깊이에 해당하는 원소를 구할 수 있습니다. 최초의 재귀 호출 시에 구간의 범위인 $[1, 2^K - 1]$과 깊이의 정보 1을 인자로 넘기고 다음의 함수를 수행합니다.

1. 전달 받은 구간 $[s, e]$의 중앙의 원소를 전달 받은 깊이의 벡터에 담는다.
2. $s$와 $e$가 같다면 반환
3. 중앙의 원소를 제한 왼쪽 구간 $[s, (s + e) / 2 - 1]$과 (현재 깊이 + 1)을 매개변수로 재귀호출
4. 중앙의 원소를 제한 오른쪽 구간 $[(s + e) / 2 + 1, e]$과 (현재 깊이 + 1)을 매개변수로 재귀호출

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 1024

using namespace std;

int k, sz, arr[MAX];
vector<int> depth[11];

void func(int s, int e, int d)
{
	depth[d].push_back(arr[(s + e) / 2]);
	
	if (s == e)
		return;

	func(s, (s + e) / 2 - 1, d + 1);
	func((s + e) / 2 + 1, e, d + 1);
}

int main(void)
{
	FASTIO;

	cin >> k;
	sz = pow(2, k) - 1;
	for (int i = 1; i <= sz; i++)
		cin >> arr[i];

	func(1, sz, 1);

	for (int i = 1; i <= k; i++)
	{
		VPRT(depth[i], int);
		cout << endl;
	}

	return 0;
}