색종이 만들기

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int blue,white;
int board[130][130];
bool check(int y, int x, int size){
    int prev = board[y][x];
    int flag=0;
    for(int i=y;i<y+size;i++)
    {
        for(int j=x;j<x+size;j++)
        {
            if(board[i][j] != prev) {
                flag = 1;
                break;
            }
        }
    }
    if(flag) return false;
    return true;
}
void color(int y, int x, int size){
    bool result = check(y, x, size);
    if(result){
        if(board[y][x]) blue++;
        else white++;
    }else{
        color(y, x, size/2);
        color(y+size/2, x, size/2);
        color(y, x+size/2, size/2);
        color(y+size/2, x+size/2, size/2);
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    color(0, 0, N);
    cout << white << '\n' << blue << '\n';
    return 0;
}

• 앞 재귀문제와 유사한 문제
• key point!
  : 입력이 2^n이기 때문에 맞춰서 size를 조정하며 탐색!