1992번 쿼드트리

문제 링크

쿼드트리

문제 풀이

사각형 안의 숫자들 모두 같은지 확인하고 같으면 멈추고 다르다면 사각형을 4개로 분할하여 재귀 호출로 푼다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int N;
vector<string> board(100);

string solve(int y, int x, int size) {
    int cnt[2] = { 0, };
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            ++cnt[board[y + i][x + j] - '0'];

    if (cnt[1] == 0) return "0";
    if (cnt[0] == 0) return "1";

    int subsize = size / 2;
    string ret = "(";
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            ret += solve(y + subsize * i, x + subsize * j, subsize);
    ret += ")";
    return ret;
}

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

    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> board[i];
    cout << solve(0, 0, N);
    return 0;
}