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

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

9934번: 완전 이진 트리

문제

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

깊이가 2와 3인 완전 이진 트리

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

 

 

이 문제는 완전 이진 트리 관련 문제이다.

완전 이진 트리의 특성을 알고 있으면 어렵지 않게 해결할 수 있다.

완전 이진 트리의 높이가 H개라면 노드의 수는 2^H-1개가 된다. 무조건 홀수개의 노드를 가질 수 밖에 없다.

문제의 예제를 한 번 보자.

높이가 3이고 상근이의 조건에 따라 주어진 노드 순서는 "1 6 4 3 5 2 7"이다.

위에 그림과 주어진 배열의 상태를 한 번 확인해보면 초기 상태의 배열의 정가운데가 루트 노드가 된다.

즉, 3이 루트 노드가 된다. 그리고 루트 노드의 양쪽 자식 노드는? 루트 노드를 기준으로 좌/우를 잘라서 또 다시 정 가운데 위치가 3의 자식 노드가 된다.

 

이렇게 해서 범위를 지정해주고, 그 범위가 몇 번째 높이에서의 루트 노드인지를 알 수 있다.

이것을 재귀함수 / 분할 정복기법으로 쉽게 해결이 가능하다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
int Tree[1030];
vector<int> answer[100];

void Divide(int l, int r, int h) {
	if (l == r) return;
	int mid = (l + r) / 2;
	answer[h].push_back(Tree[mid]);

	Divide(l, mid, h + 1);
	Divide(mid+1, r, h + 1);
}

int main() {
	CUNLINK;
	cin >> N;
	int Area = (int)pow(2, N) - 1;
	for (int i = 0; i < Area; i++)
		cin >> Tree[i];
	Divide(0, Area - 1, 0);
	answer[N - 1].push_back(Tree[Area - 1]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < answer[i].size(); j++) {
			cout << answer[i][j] << " ";
		}
		ENDL;
	}
	
	return 0;
}