[백준 1780] 종이의 개수 (C++)

이 문제는 종이를 반복적으로 분할해나가며, 해당 섹션에 적힌 숫자가 모두 같은지 확인해야하는 문제이다.

따라서, 섹션을 확인하는 과정과 섹션을 분할하는 과정이 필요할 것이다.

그리고, 섹션에 적힌 숫자가 모두 일치하지 않다면, 섹션을 9등분하여 다시 확인해야하므로 재귀임이 자명해보인다.

먼저, 섹션에 적힌 숫자가 모두 일치하는지 확인하는 과정을 생각해보자.

만약, 섹션의 좌측 상단인 $(r, c)$를 기준으로 $sz$크기의 섹션의 숫자가 모두 같다면, 기준점인 $(r, c)$와 동일할 것이다. 만약, 동일하지 않은 칸이 존재하면, 이 섹션에 적힌 숫자는 모두 같지 않음이 자명하다.

다음으로, 섹션을 9등분 하는 방법을 고민해보자.

다음 섹션의 크기는 $\displaystyle\frac{sz}{3}$가 될 것이고, 섹션의 기준점은 $(r, c)$, $(r, c + \displaystyle\frac{sz}{3})$, $(r, c + \displaystyle\frac{2sz}{3})$, $(r + \frac{sz}{3}, c)$, $(r + \displaystyle\frac{sz}{3}, c + \displaystyle\frac{sz}{3})$, $(r + \displaystyle\frac{sz}{3}, c + \displaystyle\frac{2sz}{3})$, $(r + \displaystyle\frac{2sz}{3}, c)$, $(r + \displaystyle\frac{2sz}{3}, c + \displaystyle\frac{sz}{3})$, $(r + \displaystyle\frac{2sz}{3}, c + \displaystyle\frac{2sz}{3})$가 될 것이다.

이 섹션들에 대해 다시 같은 과정을 진행해주면 된다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, cnt[3], board[2200][2200];

bool check(int sz, int r, int c) {
    for (int i = r; i < r + sz; i++) {
        for (int j = c; j < c + sz; j++) {
            if (board[i][j] != board[r][c]) return 0;
        }
    }
    return 1;
}

void solve(int sz, int r, int c) {
    if (check(sz, r, c)) {
        cnt[board[r][c] + 1]++;
        return;
    }
    
    int nsz = sz / 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            solve(nsz, i * nsz + r, j * nsz + c);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> board[i][j];
    }
    
    solve(n, 0, 0);
    
    for (int i = 0; i < 3; i++) cout << cnt[i] << "\n";
}