[BAEKJOON] 9934_완전 이진 트리_C언어

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

풀이
문제의 이름대로 두 갈래씩 갈라지면서 주어진 조건에 맞게 트리를 출력하는 문제이다.

문제에서 주어진 입력에 대한 탐색 순서를 나타내었다.

1. 우선 트리의 가장 왼쪽 끝인 1번 노드로 간다.

2. 그 후 더 진행할 노드가 없으므로 6번 노드를 방문한다.

3. 왼쪽은 이미 방문했으니 4번 노드로 간다.

4. 4번노드 방문 후 6번 노드를 방문했으므로 3번 노드로 간다.

5. 3번 노드에서 왼쪽은 이미 다 방문 했으므로 오른쪽으로 갈래의 노드로 내려간다.

6. 이 경우로 왼쪽 끝 노드인 5번 노드를 우선적으로 방문 한다.

7. 5번 노드에서 더 내려갈 곳이 없으므로 5번 노드를 나와 2번 노드를 방문한다.

8. 마지막으로 방문하지 않은 오른쪽 노드를 방문 후 탐색을 종료한다.

 

나는 층별로 나누어 방문한 곳을 저장 후 출력하였다.

근데 문제에서 총 10층까지 입력을 받는다고 하여서 tree[10][1000]이런 식으로 이 차원 배열을 만들어서 사용해도 되지만...뭔가 비효율 적인 것 같아 10층 까지 입력을 받으면 노드의 개수가 1023개 이므로

tree[1024]만 선언한 후, 각 층을 구분지어주기 위한 L[11] = ;을 이용하여 층을 구분하였다.

 

 

/* 인덱스값으로 층을 구분.0 1층   1~2 2층   3~6 3층   7~14 4층   15~30 5층  
31~62 6층   63~126 7층   127~254 8층   255~510 9층   511~1022 10층

 

*/

 

K값 2-5까지 입력한 예제와 출력값.

 

2

2 1 3

 

3

1 6 4 3 5 2 7

 

4

1 9 2 13 3 10 4 15 5 11 6 14 7 12 8

 

5

 

1 17 2 25 3 18 4 29 5 19 6 26 7 20 8 31 9 21 10 27 11 22 12 30 13 23 14 28 15 24 16

 

작성한 코드

#include <stdio.h>
int front,check[1024], tree[1024], L[11] = {0,1,3,7,15,31,63,127,255,511,1023};
int K;
/*
0 1층   1~2 2층   3~6 3층   7~14 4층   15~30 5층   31~62 6층   63~126 7층   127~254 8층   255~510 9층   511~1022 10층
*/
 
void T(int layer)
{
    if (layer > K) return;
    if (layer == K-1) {
        tree[L[layer]] = check[front++];
        L[layer] = L[layer] + 1;
        return;
    }
    T(layer + 1);//트리의 왼쪽으로
 
    tree[L[layer]] = check[front++];//왼쪽트리 나온 후 값을 저장
    L[layer] = L[layer] + 1;
 
    T(layer + 1);//트리의 오른쪽으로
 
    return;
}
 
int main()
{
    scanf("%d",&K);
 
    for (int i = 0; i < L[K]; i++)
        scanf("%d",&check[i]);
 
    T(0);
 
    int t=0,n = 1;//t는 tree의 인덱스, n은 층마다 반복 회수
    for (int i = 0; i < K; i++)//출력함수
    {
        for (int j = 0; j <n ; j++)
        {
            printf("%d ", tree[t]);
            t++;
        }
        n *= 2;
        printf("\n");
    }
    return 0;
}