사각형 안에 저장된 수가 모두 같다면 그대로 사용하고, 다른 경우 이를 9개로 나누는 문제이다. 사각형 안의 수를 보고 다 같다면 멈추고, 아닐 시 범위를 나눠어 9번의 재귀 호출을 하면 된다.
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int N;
vector<int> ans(3, 0);
vector<vector<int>> board(3000, vector<int>(3000, 0));
void solve(int y, int x, int size) {
int cnt[3] = { 0, };
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
++cnt[board[y + i][x + j] + 1];
for (int i = 0; i < 3; ++i) {
if (cnt[i] == size * size) {
++ans[i];
return;
}
}
int subSize = size / 3;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
solve(y + subSize * i, x + subSize * j, subSize);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> board[i][j];
solve(0, 0, N);
for (int i = 0; i < 3; ++i)
cout << ans[i] << endl;
return 0;
}