(SWEA c++)7985. Rooted Binary Tree 재구성

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWu1JmN6Js4DFASy&categoryId=AWu1JmN6Js4DFASy&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=6 

SW Expert Academy

 

주어진 배열을 이진 트리의 중위 순회 방식으로 출력.

K = depth를 뜻하므로, 배열의 원소를 방문하면서 count를 세어 pow(2, depth)라면 개행처리를 해야 한다.

 

트리이기 때문에 BFS를 이용.

배열 원소의 접근은 front와 back의 절반에 위치하는 인덱스다.

이 인덱스를 출력하고, 이진 탐색처럼 범위를 좁혀나가면 된다.

 

즉, front와 back을 큐에 넣어주면서 같은 depth에 해당하는 원소를 출력하면 된다.

시작은 0 ~ 2 ^ K로 한다. 또한, depth를 0으로 하여 같이 큐에 넣어준다.

 

while문으로 큐가 빌 때까지 진행.

큐의 맨 앞부분에서 원소를 꺼내고

차례대로 front, back, depth라는 변수에 데이터를 저장한다.

 

pop()을 하여 큐의 데이터를 하나씩 지워주고,

v[mid]를 출력하여 중위 순회의 부모 노드를 출력한다.

 

만약 front == mid 이거나 back == mid라면, 자식 노드가 없다는 뜻이 되므로 continue 처리를 한다.

그렇지 않다면 큐에 계속해서 넣어줘야 한다.

 

큐에 데이터를 넣을 때에는 count를 이용한다.

count는 현재 depth의 노드 개수를 뜻한다.

count와 2 ^ depth가 같다면 모든 노드를 출력했기 때문에 개행 처리와 함께 count = 1로 초기화한다.

그렇지 않다면 count++만 하여 노드 개수를 늘려나간다.

 

while문이 끝나면 다음 테스트 케이스를 처리하기 위해 개행 처리를 한번 해주면 된다!

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int main(int argc, char **argv)
{
    int test_case;
    int T;

    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        queue<pair<pair<int, int>, int>> q;
        vector<int> v;
        int count = 1;
        int n;
        int K;

        cin >> K;

        for (int i = 0; i < pow(2, K) - 1; i++)
        {
            cin >> n;
            v.push_back(n);
        }

        cout << "#" << test_case << " ";

        q.push({{0, v.size()}, 0});

        while (!q.empty())
        {
            pair<pair<int, int>, int> p = q.front();
            int front = p.first.first;
            int back = p.first.second;
            int depth = p.second;
            int mid = ((front + back) / 2);

            q.pop();

            cout << v[mid] << " ";

            if (front == mid || back == mid)
            {
                continue;
            }

            q.push({{front, mid}, depth + 1});
            q.push({{mid + 1, back}, depth + 1});

            if (count == pow(2, depth))
            {
                cout << endl;
                count = 1;
            }
            else
            {
                count++;
            }
        }
        cout << endl;
    }

    return 0;
}