백준 9934 완전 이진 트리 c++ (트리)

문제 출처 : 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 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.

출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

알고리즘 분류

• 구현
• 트리
• 재귀

풀이

기존에 트리에서 사용하던 dfs를 이용한 경로 탐색은 모두 '전위순회' 방식으로 탐색하였다.

오늘 처음 '중위순회' 방식의 탐색을 구현했으며, 방식은 다음과 같다.

'중위순회'방식은 문제에서 설명한 상근이가 빌딩에 들어가는 순서와 일치한다.

가장 하위 레벨의 왼쪽 노드부터 방문하고, 그 부모를 방문하고, 현재의 오른쪽 노드를 방문하며 위로 올라가는 방식이다. 따라서, 방문 순서의 가운데는 항상 루트 노드인 것을 알 수 있다. 

주어진 예제를 살펴보자.

k =3, depth=1

val	1	6	4	3	5	2	7
idx	0	1	2	3	4	5	6

 주어진 방문 순서를 크기가 인덱스가 0<=idx<7인 배열로 나타낸 것이고, 루트 노드는 (0+7)/2 인덱스에 있는 값인 3이 된다.

k=3, depth=2

val	1	6	4	3	5	2	7
idx	0	1	2	3	4	5	6

'중위순회' 방식은 왼쪽 자식 노드부터 방문한다고 했다. 따라서 현재 노드는 루트 노드인 3이었고, 3의 왼쪽에 있는 값들이 루트 노드의 왼쪽 자식 노드일 것이고, 3의 오른쪽에 있는 값들이 루트 노드의 오른쪽 자식 노드일 것이다.

 

k=3, depth=2

val	1	6	4	3	5	2	7
idx	0	1	2	3	4	5	6

루트 노드의 왼쪽 자식 노드들이 속한 idx 0~2의 값들을 보면, '중위순회'의 방식을 따라, 가운데 있는 6이 루트노드의 왼쪽 자식 노드가 될 것이고,

루트 노드의 오른쪽 자식 노드들이 속한 idx 4~6의 값을 보면, 가운데 있는 2가 루트노드의 오른쪽 자식 노드가 될 것이다.

남은 1은 6의 왼쪽 자식 노드, 4는 6의 오른쪽 자식 노드, 5는 2의 왼쪽 자식 노드, 7은 2의 오른쪽 자식 노드가 된다.

 

이를, 재귀를 이용한 분할 정복 기법으로 구현할 수 있으며, 재귀의 깊이는 곳 트리의 깊이가 된다.

 

 

코드

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

//1<=k<=10
//2^k
int input[10024];
int k;
vector<int> arr[10];
void insertTree(int depth,int start, int end) {
	
	if (start >= end) {
		return;
	}
	int mid = (start + end) / 2;
	arr[depth].push_back(input[mid]);
	insertTree(depth + 1, start, mid);
	insertTree(depth + 1, mid+1, end);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> k;
	
	
	int num;
	int idx = 0;
	while (cin >> num) {
		input[idx++] = num;
	}
	insertTree(0,0, idx);
	for (int i = 0; i < k; i++) {
		for (auto o : arr[i]) {
			cout << o << ' ';
		}
		cout << '\n';
	}
	return 0;
}