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

1992번: 쿼드트리

분할 정복을 이용한 문제이다. 먼저 반복문을 돌면서 n 크기만큼 합을 구해 모두 0 또는 1로 되어있는지 확인한다. 모두 0 또는 1로 되어있지 않다면 4 구역으로 나누어 다시 함수를 호출하고 이를 반복한다.
어렵지 않게 풀 수 있었던 문제였다. 생각하는 시간을 좀 더 줄여야겠다.

#include <iostream>

using namespace std;

int N;
int A[64][64];

void dfs(int y, int x, int n) {
    int sum = 0;

    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            sum += A[i][j];
        }
    }

    if (sum == 0) {
        cout << 0;
    }
    else if (sum == n * n) {
        cout << 1;
    }
    else {
        cout << "(";
        dfs(y, x, n / 2);
        dfs(y, x + n / 2, n / 2);
        dfs(y + n / 2, x, n / 2);
        dfs(y + n / 2, x + n / 2, n / 2);
        cout << ")";
    }
}

void solution(){
    dfs(0, 0, N);
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            A[i][j] = s[j] - '0';
        }
    }

    solution();

    return 0;
}