백준[1780] - 종이의 개수

문제

백준 1780 문제 보기

접근 방법

분할 정복으로 풀리는 문제이다. 처음 받은 정사각형을 검사한 뒤 다른 숫자가 있으면 9분할하여 다시 검사를 진행한다. -1은 배열에 잡히지 않으므로 모든 값은 +를 해줘 0, 1, 2 형태로 검사한다.

코드

#include <iostream>
#include <cstring>

using namespace std;
int N;
int map[2200][2200];
int ans[3];

bool check(int r, int c, int num) {
    int test = map[r][c];
    for(int i = r; i < r + num; i ++) {
        for(int j = c; j < c + num; j ++) {
            if(test != map[i][j])
                return false;
        }
    }
    return true;
}

int divide(int r, int c, int num) {
    if(check(r, c, num)) {
        ans[map[r][c]] += 1;
    } else {
        int newsize = num / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                divide(r + newsize*i, c + newsize*j, newsize);
            }
        }
    }
    return 0;
}

int main() {
    cin >> N;
    memset(ans, 0, sizeof(ans));
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            int num;
            cin >> num;
            num ++;
            map[i][j] = num;
        }
    }

    divide(0, 0, N);

    cout << ans[0] << endl;
    cout << ans[1] << endl;
    cout << ans[2] << endl;
    return 0;
}