[백준 c++] 1992 쿼드트리

문제 설명

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

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

아이디어

계속 같은 함수가 반복되는거니까 분할 정복으로 풀 수 있다.

전체 코드

#include <iostream>
#include <string>
using namespace std;
string a[64];

void quard(int size, int y, int x)
{
    char curr = a[y][x];

    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (a[i][j] != curr)
            {
                cout << '(';
                quard(size / 2, y, x);
                quard(size / 2, y, x + size / 2);
                quard(size / 2, y + size / 2, x);
                quard(size / 2, y + size / 2, x + size / 2);
                cout << ')';
                return;
            }
        }
    }
    cout << curr;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    quard(N, 0, 0);
    return 0;
}