[BOJ] 1992번 | 쿼드트리 (C++)

🔗문제 보러가기

1992번: 쿼드트리

 

🧑🏻‍💻풀이 과정

🔗2630번 문제와 유사하게 풀 수 있습니다.

전체 2차원 배열을 image라고 하고, 현재 탐색 중인 사각형 영역의 제일 왼쪽 위 시작점을 (rowBegin, colBegin)이라고 하겠습니다.

1. \(N \times N \) 크기부터 시작하여 Top-down으로 내려 간다.
2. N == 1이라면, 정답 문자열에 현재 색깔(image[rowBegin][colBegin])을 추가하고 종료한다.
3. N != 1이라면, 현재 사각형 영역이 모두 같은 색깔인지 파악하여 압축이 가능한지 알아본다.
   • 압축이 가능하다면, 정답 문자열에 현재 사각형 영역의 색깔을 추가하고 종료한다.
4. 현재 사각형 영역이 모두 같은 색이 아니라면, 정답 문자열에 '('을 추가한다.
5. N = N / 2를 적용한다.
6. 현재 사각형을 다시 4등분하여, rowBegin과 colBegin을 다음과 같이 갱신하여 재귀를 시작한다.
   • 왼쪽 위 : (rowBegin, colBegin)
   • 오른쪽 위 : (rowBegin, colBegin + N)
   • 왼쪽 아래 : (rowBegin + N, colBegin)
   • 오른쪽 아래 : (rowBegin + N, colBegin + N)
7. 정답 문자열에 ')'을 추가한다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <string>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
const char UNCOMPRESSIBLE = '?';

char IsAvailableCompress(const vector<string>& image, int N, int rowBegin, int colBegin)
{
    char color = '?';

    for (int row = rowBegin; row < rowBegin + N; row++)
    {
        for (int col = colBegin; col < colBegin + N; col++)
        {
            if (row == rowBegin and col == colBegin)
            {
                color = image[row][col];
                continue;
            }

            if (image[row][col] != color)
                return UNCOMPRESSIBLE;
        }
    }

    return color;
}

void Compress(const vector<string>& image, string& result, int N, int rowBegin, int colBegin)
{
    if (N == 1)
    {
        result += image[rowBegin][colBegin];
        return;
    }

    char flag = IsAvailableCompress(image, N, rowBegin, colBegin);
    
    if (flag != UNCOMPRESSIBLE)
    {
        result += flag;
        return;
    }

    result.push_back('(');
    N /= 2;

    Compress(image, result, N, rowBegin, colBegin);             // 왼쪽 위
    Compress(image, result, N, rowBegin, colBegin + N);         // 오른쪽 위
    Compress(image, result, N, rowBegin + N, colBegin);         // 왼쪽 아래
    Compress(image, result, N, rowBegin + N, colBegin + N);     // 오른쪽 아래

    result.push_back(')');
}


int main()
{
    FAST_IO
    int N;
    cin >> N;

    vector<string> bwImage(N);
    for (int i = 0; i < N; i++)
        cin >> bwImage[i];


    string answer = "";
    Compress(bwImage, answer, N, 0, 0);

    cout << answer;
    return 0;
}