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

9월 7일(목) - 트리 (9934번)

9934번: 완전 이진 트리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 완전 이진 트리이기에 중앙값을 차례대로 저장해나간다면, 원하는 출력의 순서를 맞출 수 있을 것

- 또한 완전 이진 트리이기에 하나의 배열에 입력받고, 합병정렬처럼 재귀를 돌려주면 될 것으로 예상

- 재귀함수에는 (start, end, 깊이)가 매개변수로 넘어와야하고, 탈출조건은 (깊이 == K)인 경우이다

- 따라서 완전 이진 트리의 최대깊이가 10이라면, 터미널 노드의 개수는 2^9개일 것 이므로

  전역변수로 완전 이진 트리의 노드를 입력받을 arr[ 1025 ]를 선언한다

- 같은 원리로 트리를 재구성하기 위한 2차원 배열도 tree[ 깊이 ][ 인덱스 ]의 구성으로 만들 것 이기에

  전역변수로 tree[ 11 ][ 1025 ]를 선언한다

 

\	idx == 0	idx == 1	idx == 2	...
깊이 == 0
깊이 == 1
...

 

- 입력은 트리의 깊이인 K, for문을 0부터 (2^K - 1)까지 돌리면서 arr[ i ]에 완전이진트리를 입력받는다

- arr[ ]를 통해 트리의 값들을 입력받았다면, tree[ 11 ][ 1025 ]에다가 재귀를 통해서 트리를 재구성해야한다

  재귀의 인수는 (start, end, 깊이)가 (0, (2^K - 1) - 1 , 0)으로 넘어간다

- 재귀함수에서는 depth == K라면 탈출하고,

  mid 인덱스값을 설정하여서 tree[ 깊이 ][ 인덱스 ]에다가 루트에 해당하는 arr[ mid ]값을 넣어준다

  이후에는 mid 인덱스값을 기준으로 앞/뒤를 나누어서 재귀를 돌린다

- 출력은 이중 for문을 돌리면서 tree[ ][ ]값을 출력해준다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

void find_root(int start, int end, int depth)
{
	if (depth == K)
	{
		return;
	}

	int mid = (start + end) / 2;
	tree[depth][idx] = arr[mid];
	idx++;

	find_root(start, mid - 1, depth + 1);
	find_root(mid + 1, end, depth + 1);
}

1. 합병정렬에서 재귀의 구성 아이디어를 얻었지만, 재귀를 위해서는 인수부분의 수정이 필요하다

-> 완전 이진 트리라서 전체가 홀수개이고, 이미 tree[ ][ ]에 저장하며 루트인 것이 증명된 mid값은 필요가없기에

    start ~ mid-1 까지 / mid+1 ~ end까지로 나누어서 재귀를 진행해야한다

 

 

2. 또한 트리를 재구성해야하고, 출력을 위해서는 2차원배열의 깊이와 인덱스값 모두 변화가 필요하다

-> 세로방향의 변화는 깊이로, 가로방향의 변화는 인덱스값으로 구현해야한다

-> 깊이는 인수부분에서 depth+1을 진행해주면되기에 세로방향의 변화는 구현했지만,

    깊이가 변하면서 새롭게 루트로 증명이되는 arr[ mid ]값을 2차원배열에 저장하기위해서는

    가로방향의 인덱스값 변화의 구현이 필요했다

 

-> 결국 처음에 tree[ ][ ]를 모두 0으로 초기화해놓고, arr[ mid ]값을 새롭게 넣게되면 idx++을 해준다

    최종출력때는 tree[ ][ ]에서 0이 아닌 값을 모두 출력하는것으로 구현했지만, 메모리사용이 비효율적인듯

-> 추후 다른 풀이 시도해봐야함

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <math.h>

int K;
int arr[1025];
int tree[11][1025] = { 0, };
// tree[ depth ] [ idx ]
int idx = 0;

void find_root(int start, int end, int depth)
{
	if (depth == K)
	{
		return;
	}

	int mid = (start + end) / 2;
	tree[depth][idx] = arr[mid];
	idx++;

	find_root(start, mid - 1, depth + 1);
	find_root(mid + 1, end, depth + 1);
}

int main(void)
{
	scanf("%d", &K);

	int num = (int)pow(2, K) - 1;
	for (int i = 0; i < num; i++)
	{
		scanf("%d", &arr[i]);
	}

	find_root(0, num - 1, 0);

	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < num; j++)
		{
			if (tree[i][j] != 0)
			{
				printf("%d ", tree[i][j]);
			}
		}
		printf("\n");
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ