(BOJ) 9934 완전 이진 트리

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

 

 

문제 풀이:

위에서부터 왼쪽에서 오른쪽으로 1번부터 순서를 매긴다고 하자.

깊이가 k일 때, 마지막 레벨의 번호는 $2^{k-1}$≤N≤$2^{k}-1$이다.

l: $2^{k-1}$

r: $2^{k}-1$ 

pos: 1 (도착 순서)

이라고 하자.

 

1. 왼쪽 노드를 방문 안했고 현재 l보다 작다면(아직 마지막 층이 아니라면) -> 왼쪽 노드로 이동

2. 왼쪽 노드를 방문 했고 현재 자신의 위치에서 방문한 적이 없으면

    -> 입력 받은 순서대로 트리의 해당 위치에 값을 넣어준다.

3. 현재 위치를 방문했고, 오른쪽 노드는 방문 하지 않았는데 현재 l보다 작다면 -> 오른쪽 노드로 이동

 

 

소스 코드:

int h,l,r,arr[1026],res[1026],pos=1;
bool visit[1026];
void func(int cur) {
	if (!visit[cur*2]&&cur< l) func(cur * 2);
	if (!visit[cur] && cur >= l && cur <= r) {
		visit[cur] = true;
		res[cur] = arr[pos++];
	}
	if (!visit[cur]&&visit[cur*2]) {
		visit[cur] = true;
		res[cur] = arr[pos++];
	}
	if (!visit[cur * 2 + 1] &&cur<l) func(cur * 2 + 1);
}

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

	cin >> h;
	for (int i = 1; i < pow(2, h); i++) {
		cin >> arr[i];
	}
	l = pow(2, h - 1); 
	r = pow(2, h) - 1;
	func(1);
	pos = 1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < pow(2, i); j++) {
			cout << res[pos++]<<" ";
		}
		cout << '\n';
	}
	return 0;
}

 

 

소스 코드: