[c++][BOJ][2630] 색종이 만들기

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

2630번: 색종이 만들기

색종이에 같은 숫자가 있는 사각형끼리 모아서 잘라내는 문제입니다.

 

가장 먼저 , 색종이가 1로만 이루어져 있는지 0으로만 이루어져 있는지 체크합니다.

 

섞여있다면 , 4등분 하고 다시 1과 0으로만 이루어져 있는지 체크합니다.

 

섞이지 않았다면 , 1 또는 0으로만 이루어져 있으므로 count를 체크합니다.

 

마지막에 1칸짜리만 남았다면 , 그 칸이 1인지 0인지 확인해서 카운트를 증가시킵니다.

#include <iostream>
using namespace std;

int arr[128][128] = {0};
int count1 = 0;
int count0 = 0;

void find(int xleft , int xright, int yleft , int yright, int index ){
    if(index == 1){
        if(arr[xleft][yleft] == 1){
            count1++;
        }
        else {
            count0++;
        }
        return;
    }
    
    bool find1 = false;
    bool find2 = false;
    
    for(int i=xleft; i<=xright; i++){
        for(int j=yleft; j<=yright; j++){
            if(arr[i][j] == 1)
                find1 = true;
            else if(arr[i][j] == 0)
                find2 = true;
            
            if(find1 == find2)
                break;
        }
    }
    
    if(find1 == find2){
        index /= 2;
        find(xleft, xleft+index-1, yleft , yleft+index-1, index);
        find(xleft+index, xright, yleft, yleft+index-1, index);
        find(xleft, xleft+index-1, yleft+index, yright, index);
        find(xleft+index, xright, yleft+index, yright , index);
    }
    else if(find1 == true){
        count1++;
    }
    else {
        count0++;
    }
}

int main(){
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }
    
    find(0 , n-1 , 0 , n-1, n);
    
    cout << count0 << '\n';
    cout << count1;
}