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

백준의 쿼드트리(1992) 문제이다.

[ 문제풀이 ]

먼저 문제에서 설명으로 나와있는 이상한 그림과 이상한 맵에서 왜 답이 그렇게 나오는지 한번 알아보고 넘어가자.

.

이 그림에 대한 정답으로 "(0(0011)(0(0111)01)1)" 이 적혀있다.

무슨 의미인지 한번 알아보자. 문제에서 이야기하는 '쿼드트리'는 "전체를 한 번에 나타내지 못하면, 왼쪽위,아래, 오른쪽 위, 아래 이렇게 4개의 영역으로 나눠서 압축" 하는 것을 이야기한다.

즉, "현재의 크기를 4개의 영역으로 나눠서 압축" 한다고 생각하면 된다.

위의 맵이 8 x 8 짜리 맵인데, 일단 가장 초기인 8 x 8 크기에서 한번 맵을 바라보자.

8 x 8 칸이 모두 0으로만 이루어져 있거나, 1로만 이루어져 있지 않다. 즉, "전체를 한번에 나타내지 못하는 경우"에 해당하는 것이다. 이런 경우에는 위의 크기를 4개의 영역으로 나눈다. 다음과 같이 !

.

이렇게 나누는 것이다. 그리고 나서 이제 4개의 영역을 개별적으로 확인을 해보자.

왼쪽 위의 그림을 1번, 오른쪽 위의 그림을 2번, 왼쪽 아래의 그림을 3번, 오른쪽 아래의 그림을 4번 이라고 해보자.

1번 그림부터 보자.

1번 그림의 경우에는 '0' 하나로만 표현이 가능하다.

2번 그림을 보자. 2번 그림 같은경우에는 '0' 혹은 '1' 하나의 값으로만 표현할 수가 없다. 따라서 4 x 4 짜리를 또 2 x 2 크기로

4개의 영역으로 나눠야 한다.

.

4개의 영역에서 똑같이 1 ~ 4번 으로 번호를 붙여보자. 1번 영역과 2번 영역은 '0' 하나로만 표현이 가능하다.

반대로 3번 영역과 4번 영역은 '1'하나로만 표현이 가능하다.

다시 4 x 4 짜리 4개로 나눈 그림에서 '3번그림'으로 돌아오자.

딱 보면 하나의 값으로 표현되지 않고 또 2x2짜리 4개의 영역으로 나눠줘야 한다.

.

이 그림에서 또 1, 2, 3, 4번으로 나눠보자. 1번 그림은 '0'으로만 표현이 가능하다.

2번 그림 같은 경우는 하나의 숫자로 표현되질 않아서 1x1짜리 4개로 나눠야만 표현이 가능하다. '0111' 로

3번 그림은 '0'으로만 표현이 가능하다.

4번 그림은 '1'로만 표현이 가능하다.

다시 4 x 4 짜리 4개의 영역에서 마지막 4번 그림을 보면 '1'로만 표현이 가능하다.

지금부터 위에서 '파랑색'으로 칠해진 글들의 숫자를 가장 위에서부터 순차적으로 나열해보자.

(0(0011)(0(0111)01)1

바로 이렇게 우리가 원하는 값이 나오는 것이다.

본인은 재귀를 통해서 4가지 영역으로 나누는 과정을 진행해 주었다.

먼저, 현재 영역이 갖는 크기가 오로지 하나의 숫자로만 표현이 가능(0 or 1) 하다면, 그대로 숫자를 출력해주고 더 이상 영역을

나누는 과정을 진행해주지 않았다.

하지만 그게 아닌 경우라면, 4개의 영역으로 나눌 필요가 있다. 그리고 이렇게 영역을 나눌 때는 '('를 통해서 표시를 해줘야 한다.

영역을 4개로 나누는 방법은 다음과 같다.

만약 현재 (x, y)에 있고, 크기가 8인 영역에 있다고 가정해보자.

이 영역을 4개로 나누려면,

(x , y , 4) , (x , y + 4 , 4) , (x + 4 , y , 4), (x + 4 , y + 4 , 4) 로 나눌 수가 있다.

즉 ! 크기를 절반으로 나누면서 알맞게 좌표값을 변경해 주면 된다.

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
#define MAX 70
using namespace std;
 
int N;
int MAP[MAX][MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++)
        {
            MAP[i][j] = S[j] - '0';
        }
    }
}
 
void DFS(int x, int y, int Size)
{
    if (Size == 1)
    {
        cout << MAP[x][y];
        return;
    }
    
    bool OnlyZero, OnlyOne;
    OnlyZero = OnlyOne = true;
    for (int i = x; i < x + Size; i++)
    {
        for (int j = y; j < y + Size; j++)
        {
            if (MAP[i][j] == 0) OnlyOne = false;
            if (MAP[i][j] == 1) OnlyZero = false;
        }
    }
 
    if (OnlyZero == true)
    {
        cout << 0;
        return;
    }
    if (OnlyOne == true)
    {
        cout << 1;
        return;
    }
 
    cout << "(";
    DFS(x, y, Size / 2);
    DFS(x, y + Size / 2, Size / 2);
    DFS(x + Size / 2, y, Size / 2);
    DFS(x + Size / 2, y + Size / 2, Size / 2);
    cout << ")";
}
 
void Solution()
{
    DFS(0, 0, N);
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}