[백준/BOJ] 1780 종이의 개수

문제 : 1780 종이의 개수

1780번: 종이의 개수

종이가 모두 같은 숫자로 이루어졌는지 확인하고

만약 다른 숫자가 포함된다면 종이를 9 등분하는 것을 반복하는 문제이다.

분할 정복을 이용해 재귀 함수 코드를 작성해

시작 좌표와 가로세로 길이를 정해준 후 반복하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, arr[2500][2500], ans[3];
void f(ll x, ll y, ll size){
    ll cnt[3]={0,};
    for (int i=x;i<x+size;i++){
        for (int j=y;j<y+size;j++){
            if (arr[i][j]==-1)
                cnt[0]++;
            if (arr[i][j]==0)
                cnt[1]++;
            if (arr[i][j]==1)
                cnt[2]++;
        }
    }
    if (cnt[0]==0 && cnt[1]==0)
        ans[2]++;
    else if (cnt[1]==0 && cnt[2]==0)
        ans[0]++;
    else if (cnt[0]==0 && cnt[2]==0)
        ans[1]++;
    else{
        ll dir[3]={0,size/3,size/3*2};
        for (int i=0;i<3;i++){
            for (int j=0;j<3;j++){
                f(x+dir[i],y+dir[j],size/3);
            }
        }
    }
}
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 >> arr[i][j];
        }
    }
    f(0,0,N);
    for (auto x:ans)
        cout << x << "\n";
    return 0;
}