백준 9934 c++ "완전 이진 트리" -PlusUltraCode-

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

 

[필자 사고]

필자는 해당 문제를 주어진 입력 배열창에 DFS로 이용하여 분활하여 접근한 뒤 mid값을 tree[][] 배열에 저장하여 

나중에 출력 하는 형태로 해당 문제를 해결했다. 

다양한 풀이 방법이 존재할거 같다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input 함수

• 사용자로부터 트리의 높이 N을 입력받습니다.
• 트리의 전체 노드 수는 완전 이진트리이므로 2^N - 1입니다. 하지만 코드에서는 배열의 인덱스를 1부터 시작하기 때문에 SIZE = 2^N으로 설정하고, arr[1]부터 arr[SIZE-1]까지 값을 입력받습니다.
• 이 입력은 중위 순회(Inorder Traversal) 결과입니다.
• 이후 tree는 각 트리의 레벨(깊이)에 해당하는 노드들을 담기 위한 2차원 벡터입니다. 총 N+1개의 레벨을 준비합니다 (1부터 시작하려고 +1 함).

---

DFS 함수

• 이 재귀 함수는 start부터 end까지의 구간에서 **중간 노드(mid)**를 현재 깊이(depth)의 루트 노드로 간주하고 tree[depth]에 저장합니다.
• 즉, 중위 순회 결과를 기반으로 트리를 재구성합니다.
• 왼쪽 서브트리는 start부터 mid-1, 오른쪽 서브트리는 mid+1부터 end로 분리하여 재귀 호출합니다.
• depth > N인 경우는 트리의 최대 깊이를 넘은 것이므로 재귀를 종료합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N;
vector<int> arr;
vector<vector<int>> tree;
int SIZE = 0;
void Input() {
	cin >> N;
	SIZE = pow(2, N);
	tree.resize(N + 1);
	arr.resize(SIZE);

	for (int i = 1; i < SIZE; i++) {
		cin >> arr[i];
	}
}

void DFS(int start, int end, int size,int depth) {

	if (depth > N)return;

	int mid = (start + end) / 2;
	tree[depth].push_back(arr[mid]);
	DFS(start, mid-1, size / 2, depth + 1);
	DFS(mid + 1, end, size / 2, depth + 1);
}

void Game_Start() {
	DFS(1, SIZE - 1, SIZE - 1,1);

	for (int i = 1; i <= N; i++) {
		for (int k = 0; k < tree[i].size(); k++) {
			cout << tree[i][k] << " ";
		}
		cout << "\n";
	}
}

int main(void) {
	Input();
	Game_Start();
}