[백준 1992] 쿼드트리(C++)

📕문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111) 01) 1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

---

📕입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

---

📕출력

영상을 압축한 결과를 출력한다.

---

🔎문제해석

앞에서 푼 종이의 개수를 풀고 푸니까 훨씬 더 쉬운 느낌?

분할 정복을 푸는 방법이 딱 정형화되어있는 거 같아서 풀면 풀수록 쉬웠다. 이 문제는 분할하고 정복하는 것은 쉽지만 조금 까다로웠던 부분이 출력 문제였다. 저렇게 특이한 형식으로 출력해야 했기에 조금 귀찮았다.

나는 처음에 괄호를 어떻게 넣어줘야 할지 몰라서 앞, 뒤로 접근이 용이한 deque를 사용했다.

하지만 지금 다시 와서 보니 deque 말고 queue도 괜찮고 vector도 괜찮았을 것 같다.!! 

어떤 자료구조를 사용해도 상관없을 것 같다. 

---

📃코드

/*
백준 실버1 쿼드트리
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
int n;
vector<vector<int>> graph;
deque<string> dq;
void makeTree(int row, int col, int Size);
bool checkTree(int row, int col, int Size);
void decideTree(int row, int col);
int main()
{
    cin >> n;
    graph.resize(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &graph[i][j]); //공백없이 한글자씩 입력받음.
        }
    }
    makeTree(0, 0, n);
    while (!dq.empty())
    {
        auto a = dq.front();
        dq.pop_front();
        cout << a;
    }
}
void makeTree(int row, int col, int Size)
{

    int tsize = Size / 2; // 4사분면은 가로와 세로를 2등분하면 된다.
    if (tsize < 1)        //더 이상 분할하지 못할 경우에는 재귀를 멈춘다.
    {
        return;
    }
    else
    {
        if (checkTree(row, col, Size) == true) //현재 기준점으로 Size만큼 배열을 탐색해서 적절한지 검사함.
        {                                      //리턴값이 true면 모든 배열의 구성요소가 같다는 뜻.
            decideTree(row, col);
            return;
        }
        else
        { //쪼개야한다면
            dq.push_back("(");
            int x[2] = {row, row + tsize};
            int y[2] = {col, col + tsize};
            // 4분면을 탐색함.
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    if (checkTree(x[i], y[j], tsize) == false)
                    {
                        makeTree(x[i], y[j], tsize);
                    }
                    else
                    {
                        decideTree(x[i], y[j]);
                    }
                }
            }
            dq.push_back(")");
        }
    }
}
bool checkTree(int row, int col, int Size) //배열이 모두 같은 원소로 구성되어있는지를 검사함.
{
    bool flag = true;
    int num = graph[row][col];
    for (int i = row; i < row + Size; i++)
    {
        if (flag == false)
        {
            break;
        }
        for (int j = col; j < col + Size; j++)
        {
            if (num != graph[i][j])
            { //다르다면
                flag = false;
                break;
            }
        }
    }
    return flag; // true면 모두 같은 원소, false면 하나라도 다른 원소가 있다는 뜻
}
void decideTree(int row, int col) //원소의 종류에 따라 dq에 넣어줌.
{
    int num = graph[row][col];
    switch (num)
    {
    case 0:
        dq.push_back("0");
        // dq.push_back(")");
        break;
    case 1:
        dq.push_back("1");
        // dq.push_back(")");
        break;
    }
}

 

✔느낀 점

• 앞선 종이의 개수를 구하는 코드에서는 if문을 남발했었지만, 지금은 더 깔끔하게(?) 짠 것 같다.
• 이제 분할하는 구간의 개수가 많아져도 저렇게 for 문을 이중으로 쓰면 쉽게 풀어질 듯
• 분할 정복 정벅 ㅋ