[알고리즘] 백준 2630 색종이 만들기

분할정복 문제이다. 반복문을 써도 되겠지만 재귀함수가 좀 더 만들기 쉬워서 재귀함수를 사용했다.

문제 접근

종이를 계속 4등분해 나가다가 면이 채워진게 확인되면 리턴하는 재귀함수를 만든다.

소스코드

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int arr[129][129];
int n;

int check_res(int num,int x,int y) {
    int chk = arr[x][y];
    for(int i = x;i<num+x;i++) {
        for(int j = y;j<num+y;j++) {
            if(chk != arr[i][j]) return 0;
        }
    }
    if(chk == 0) {
        return 1;
    }
    if(chk == 1) {
        return 2;
    }
}

int res1 = 0,res2=0;

void func(int num,int x,int y) {
    if(num == 1) {
        if(arr[x][y] == 1) res2++;
        else res1++;
        return;
    }
    int tmp = check_res(num,x,y);
    if(tmp == 1) {
        res1++;
        return;
    }
    if(tmp == 2) {
        res2++;
        return;
    }
    for(int i = 0;i<2;i++) {
        for(int j = 0;j<2;j++) {
            func(num/2,x+num/2*i,y+num/2*j);
        }
    }
}

int main() {
    scanf("%d",&n);
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<n;j++) {
            scanf("%d",&arr[i][j]);
        }
    }
    func(n,0,0);
    printf("%d\n%d",res1,res2);
}