[백준] 2630번 색종이 만들기 c++

재귀로 접근한다.

basic step

1. n==1 인 경우, 즉 한칸까지 탐색범위가 좁아졌을 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

2. 모든 색종이가 같은 색일 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

 

Recursive step

basic step에 해당하지 않아서 탐색범위를 좁어야 하는 경우,

해당 시점을 기준으로 4등분한 solve()를 각각 콜한다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int a[128][128]={0,};
int white = 0;
int blue = 0;

void solve(int x, int y, int n){

    if (n == 1){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }

    bool res = true;
    for (int i = x; i < x+n; i++)
    {
        for (int j = y; j < y+n;  j++){
            if(a[i][j] != a[x][y]){
                res = false;
            }
        }
    }

    if(res){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }else{
        solve(x, y, n / 2);
        solve(x, y + n / 2, n / 2);
        solve(x + n / 2, y, n / 2);
        solve(x + n / 2, y + n / 2, n / 2);
        return;
    }
    return;
}

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 << white << endl;
    cout << blue << endl;
}