[BOJ]9934 : 완전 이진 트리 C++ 문제 풀이

백준 9934번

: 완전 이진 트리

 

 

재귀 호출을 사용해서 left와 right값을 업데이트 해 center값을 정하는 과정으로 생각.

//9934 완전 이진 트리
#include <iostream>
#include <cmath>
using namespace std;

void findCenter(int * arr, int left, int right) {
	int center = (left + right) / 2;

	if (left == right) {
		cout << arr[center];
		return;
	}
	cout << arr[center];
	findCenter(arr, left, center - 1);
	findCenter(arr, center + 1, right); 

}

int main()
{
	int k;
	cin >> k;
	int size_k = pow(2, k) - 1;
	int* arr = new int[size_k];
	for (int i = 0; i < size_k; i++) {
		cin >> arr[i];
	} // 1 6 4 3 5 2 7
	
	findCenter(arr, 0, size_k - 1);

	return 0;
}

초안 코드, array의 왼쪽부터 우선 탐색해서 3 6 2 1 4 5 7 이렇게 답이 나와야 하는데 3 6 1 4 2 5 7 이렇게 노드에 대해서 왼쪽, 오른쪽을 먼저 출력하는 버그가 발생했다. 

 결국 왼쪽 이분 탐색을 호출하고, 바로 오른쪽 이분 탐색을 수행해야 하는 상황인 것이다.

//9934 완전 이진 트리
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int k;
vector <int> order;
vector <int> answer[11];

void findCenter(int left, int right, int depth) {
	if (depth == k)
		return;
	if (left == right) {
		answer[depth].push_back(order[left]);
		return;
	}
	int center = (left + right) / 2;
	answer[depth].push_back(order[center]); 
	findCenter( left, center - 1, depth + 1);
	findCenter(center + 1, right, depth + 1); 
}

int main()
{
	cin >> k;
	int size_k = pow(2, k) - 1; // 노드의 개수
	for (int i = 0; i < size_k; i++) {
		int num; cin >> num;
		order.push_back(num);
	} // 1 6 4 3 5 2 7
	
	findCenter(0, order.size(), 0);

	// 깊이에 따라 출력
	for (int i = 0; i < k; i++) { // overflow 에러
		for (int j = 0; j < answer[i].size(); j++) {
			cout << answer[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

방식을 바꾸어서, order배열과 answer배열로 나누어 문제를 풀었다. 문제의 핵심은 depth변수를 따로 둬서, answer 벡터에 이차원 벡터의 형식으로 넣는 것이다. 이전에 사용했던 방식은 노드 간의 깊이를 따로 확인할 수 없어서 출력에 어려움이 있었지만, answer벡터에 depth 별로 다르게 push_back을 진행해 재귀 호출 시에도 depth+1로 스택에 쌓이는 순서에 따라 나누어서 answer벡터에 담을 수 있었다.