[백준 9934 C++][S1] 완전 이진 트리

⭐️ 난이도

Silver 1

---

⭐️ 문제

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

9934번: 완전 이진 트리

 

---

⭐️ Idea flow

 

먼저 이 문제에 써져 있는 설명을 보면 상근이가 어떤 순서로 도시를 방문하는지에 대한 규칙이 적혀있다.

간단하게 정리를 해보자면

1. 왼쪽 자식이 있다면 왼쪽 자식이 없을 때까지 방문을 하고 해당 노드를 방문한다.

2. 왼쪽 자식들을 모두 방문 했다면, 현재의 노드를 방문한다.

3. 현재 노드를 방문했다면, 오른쪽 자식을 방문한다.

 

즉, 왼쪽 자식 -> 루트 -> 오른쪽 자식 방식으로 방문하며 이와 같은 순회를 중위 순회라고 한다.

 

이 문제에서 잊지 말아야 할 것은, 주어지는 숫자는 빌딩의 번호일 뿐, 해당 번호를 바탕으로 트리에 삽입하면 안된다는 것이다.

처음에는 tree 구조체와 tree에 노드를 삽입하는 insert 함수를 작성하여 이를 이용하려고 했다.

하지만 이진 트리에서 노드를 삽입할 때에, 노드의 값에 따라서 위치가 정해져서 사용하는데에 무리가 있다고 판단했다.

 

vector<vector<int>> tree처럼 vector 컨테이너를 이중으로 선언해서 사용한다.

tree[i][k]의 경우, 깊이 i번째에 값이 k인 노드가 있다는 뜻이다.

 

위에서 말했던 것 처럼 중위 순회는 루트 노드를 중간에 방문하는 순회 방법이므로, 중간 값이 바로 루트 값일 것이다.

이후엔 [처음~중간-1], [중간+1~끝]으로 범위를 나누고 각각의 범위에서 다시 중간 값을 찾는다.

이와 같은 방식을 재귀 함수로 작성하여 실행한다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 9934 - 완전 이진 트리
int k = 0;
vector<int> num;
vector<vector<int>> tree;

void input(){
    cin >> k;
    int tree_size = pow(2, k) - 1;

    num.assign(tree_size, 0);
    tree.assign(k, vector<int>(0,0));

    for(int i = 0; i < tree_size; i++){
        cin >> num[i];
    }
}

// root 노드들을 먼저 추출
void setTree(int left, int right, int depth){
    if(left == right){
        tree[depth].emplace_back(num[left]);
        return;
    }
    int mid = (left + right) / 2;
    tree[depth].emplace_back(num[mid]);

    setTree(left, mid - 1, depth + 1); // left subtree부터 탐색
    setTree(mid + 1, right, depth + 1);
}

void level_traversal(){
    for(int i = 0; i < k; i++){
        for(auto iter = tree[i].begin(); iter != tree[i].end(); iter++){
            cout << *iter << ' ';
        }
        cout << '\n';
    }
}

int main(){

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

    input();

    setTree(0, num.size() - 1, 0);
    level_traversal();


    return 0;
}