백준 9934_완전 이진 트리 문제풀이 in C++

2022년 11월 17일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

백준 : 9934_완전 이진 트리

문제 요구사항

---

• 첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.
• 둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다.
• 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.
• 총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다.
• 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

접근 방법

---

• 완전 이진 트리의 노드 개수는 2^Depth( 문제에선 K ) -1이다. 즉, K가 3이라면 노드 개수는 7개가 된다.
• 그렇담 문제에서 주어진 노드들을 배열에 담아 가운데 인덱스부터 접근해 재귀로 인덱스를 2로 나누며 접근하면, 왼쪽, 오른쪽 노드를 차례로 방문해 완전 이진 트리를 나타내는 벡터 answer를 만들 수 있다.

풀이 순서

---

1. K를 입력 받아 pow 함수를 이용해 Node의 개수를 구한다
2. Node의 개수만큼 for문을 반복해 노드 정보를 배열에 저장한다.
3. 트리의 최상단 루트를 기준으로 탐색하며, vector에 순서대로 담아준다.
4. 루트 노드 idx는 start_idx와 end_idx를 더하고 2로 나눈 값이 된다. answer의 depth 인덱스에 tree[ 루트 노드 idx ] 값을 넣는다.
5. 이후 반복해서 왼쪽 노드 탐색, 오른쪽 노드 탐색을 이어간다.

소스코드

---

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int K, nodeCnt;
int tree[1025];
vector<int> answer[100];

void input() {
	cin >> K;

	nodeCnt = pow(2, K) - 1;
	for (int i = 0; i < nodeCnt; i++) {
		cin >> tree[i];
	}
}

void solution(int start, int end, int depth) {
	if (start == end) {
		answer[depth].push_back(tree[start]);

		return;
	}
	int idx_rootNode = (start + end) / 2;
	answer[depth].push_back(tree[idx_rootNode]);

	solution(start, idx_rootNode, depth + 1);
	solution(idx_rootNode + 1, end, depth + 1);
}

void output() {
	for (int i = 0; i < K; i++) {
		for (int j : answer[i]) {
			cout << j << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution(0, nodeCnt -1, 0);
	output();

	return 0;
}

문제 풀이 결과

---