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

--------------------------------------------------------------------------------------------------------------------------------------------------

문제 풀이

1. 해당 문제는 주어진 데이터를 바탕으로 이진 트리를 구성하고, 각 노드를 Depth(깊이)별로 나누어 층(Level)을 구성하는

문제로 판단했다.

2. depth 별로 나누면서 계속 층을 나누면서 탐색하기 위해서는 dfs 알고리즘을 떠올랐고 재귀 함수를 통해 이진 트리를 구현했다.

----------------------------------------------------------------------------------------------------------------------------------------------------

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 


void Binary_Tree(vector<int> _vec, int _iCurrentLevel, vector<vector<int>>& _vecNode)
{
	
	if(_vec.size() <= 2)
	{
		for (auto& iter : _vec)
		{
			_vecNode[_iCurrentLevel + 1].push_back(iter); // 나머지 노드 넣기
		}
	}

	else
	{
		_vecNode[_iCurrentLevel+1].push_back(_vec[_vec.size() / 2]); // 부모 노드 

		auto iterator = find(_vec.begin(), _vec.end(), _vec[_vec.size() / 2]);
		_vec.erase(iterator);


		if (_vec.size() > 2)
		{
			vector<int> vecLeft(_vec.begin(), _vec.begin() + _vec.size() / 2);
			vector<int> vecRight(_vec.begin() + _vec.size() / 2, _vec.end());

			Binary_Tree(vecLeft, _iCurrentLevel + 1, _vecNode);
			Binary_Tree(vecRight, _iCurrentLevel + 1, _vecNode);
		}

		else
		{
			if (_vec.size() > 0)
			{
				for (auto& iter : _vec)
				{
					_vecNode[_iCurrentLevel + 2].push_back(iter); // 나머지 노드 넣기
				}
			}

		}
	}

	

}


int main()
{
	int Level_Count; 

	cin >> Level_Count;

	vector<int> m_vec; 
	vector<vector<int>> m_vecNode(Level_Count); 


	for (int i = 0; i < (1 << Level_Count) - 1; i++)
	{
		int iNumber;
		cin >> iNumber; 
		m_vec.push_back(iNumber);
	};

	m_vecNode[0].push_back(m_vec[m_vec.size() / 2]); // 루트노드 

	int m_iCurrentLevel = 0; 

	
	vector<int> vecLeft(m_vec.begin(), m_vec.begin() + m_vec.size()/2);
	vector<int> vecRight(m_vec.begin() + m_vec.size()/ 2 + 1, m_vec.end());

	if (vecLeft.size() > 0)
	{
		Binary_Tree(vecLeft, m_iCurrentLevel, m_vecNode);
		Binary_Tree(vecRight, m_iCurrentLevel, m_vecNode);
	}
	// 재귀 사용


	for(auto& iter_vector : m_vecNode)
	{
		for(auto& iter : iter_vector)
		{
			cout << iter << " ";
		}

		cout << '\n';
	}


	return 0; 
}