[C/C++] 백준 1992번 - 쿼드트리

1992번: 쿼드트리

이 문제는 사각형을 같은 색으로만 구성된 작은 사각형이 될 때까지 네 등분하는 문제이다.

분할 정복의 방법으로 해결할 수 있다.

처음 상황에서는 분할을 해야 하기 때문에 괄호를 출력한다.

이 경우 3번째 사각형은 분할을 할 필요가 없으므로 괄호는 출력하지 않고 현재 사각형의 색만 출력한다.

나머지 사각형은 분할을 해야하므로 괄호를 출력하고 서브 사각형으로 넘어간다.

 

이 과정을 사각형의 크기가 1이 될 때까지 재귀적으로 분할하면 된다.

#include <iostream>
#include <string>
using namespace std;
#define endl '\n'
#define SIZE 65
#define WHITE 0
#define BLACK 1

int N;
int map[SIZE][SIZE];

void initInput() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        string input; cin >> input;
        for (int j = 0; j < N; j++)
            map[i][j] = input[j] - '0';
    }
}

void divide(int y, int x, int size) {
    if (size == 1) {
        cout << map[y][x];
        return;
    }

    int nSize = size / 2;
    bool flag = 1;
    int curColor = (map[y][x] == WHITE ? WHITE : BLACK);
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (curColor != map[i][j]) {
                flag = 0;
                break;
            }
        }
    }
    if (flag) {
        cout << curColor;
        return ;
    }

    cout << '(';
    divide(y, x, nSize);
    divide(y, x + nSize, nSize);
    divide(y + nSize, x, nSize);
    divide(y + nSize, x + nSize, nSize);
    cout << ')';
}

void solve() {
        divide(0, 0, N);
}

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

    return 0;
}