백준 1780 종이의 개수(c++)

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

이 문제는 분할 정복 알고리즘의 대표적인 예시가 되는 문제라고 생각합니다. N*N 크기의 행렬로 표현되는 종이를 9 등분해서 나온 종이가 모두 같은 숫자이면 해당 숫자의 개수를 1 늘려줍니다. 그렇지 않으면 다시 9등분 해줘서 다시 같은 숫자가 나오는지 확인해야 합니다.

 

테스트케이스를 예시를 들어서 설명드리겠습니다.

 

<입력>

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

<출력>

10
12
11

다음 9*9 크기의 행렬에서 9등분을 하게 되면, 다음과 같은 부분은 종이의 숫자가 모두 같습니다. 

0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0

 다음 부분은 3*3 행렬에서 종이의 숫자가 모두 같지 않기에 다시 9등분 하게 됩니다. 

0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

0의 개수 8개, 1의 개수 9개, -1의 개수 9개입니다. 총숫자의 개수는 출력 예시와 같습니다.

 

<코드>

#include <iostream>

using namespace std;
int a[2200][2200];
int cnt[3];

bool same(int x, int y, int n)
{
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++)
        {
            if (a[x][y] != a[i][j])
            {
                return false;
            }
        }
    }
    return true;
}
void solve(int x, int y, int n)
{
    if (same(x, y, n))
    {
        if (a[x][y] == -1)
        {
            ++cnt[0];
        }
        else if (a[x][y] == 0)
        {
            ++cnt[1];
        }
        else
        {
            ++cnt[2];
        }
        return;
    }
    int m = n / 3;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            solve(x + i * m, y + j * m, m);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    solve(0, 0, n);
    cout << cnt[0] << '\n';
    cout << cnt[1] << '\n';
    cout << cnt[2] << '\n';
}