[BOJ / C++] 2630 : 색종이 만들기

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

분할 정복과 재귀를 사용해서 푸는 문제다.

먼저 머릿속으로 알고리즘을 생각해보았다

1. 맨 왼쪽 위 색깔에 대해 전체가 모두 0인지, 1인지 확인한다.
2. 만약 모두 0이면, white_cnt를 ++하고 종료한다.
3. 만약 모두 1이면, blue_cnt를 ++하고 종료한다.
4. 그렇지 않다면, 한 변이 2/n 인 사각형에 대해 다시 한번 검사한다.
5. 이를 반복한다.

그런데, 여기서 모두 0인지 1인지 검사를 하는게 아니라 맨 왼쪽 위의 애 색깔에 따라서 검사하는게 더 좋아보였다.

맨 윈쪽 애가 파란색인데, 하나라도 하얀색이 나오면 chk를 하고 반으로 나눠버리는거지.

#include <iostream>
#include <algorithm>

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

int n;
int white_cnt, blue_cnt;
int a[128][128];
void solve();
void count(int y, int x, int size);

int main(){
    fastio;
    solve();
    return 0;
}

void solve(){
    cin >> n;
    for(int i = 0 ; i < n; i++)
        for(int j = 0 ; j < n; j++)
            cin >> a[i][j];

    count(0, 0, n);
    cout << white_cnt << '\n' << blue_cnt << '\n';
}

void count(int y, int x, int size){
    //y, x는 현재 탐색하고자 하는 사분면의 가장 왼쪽 위의 좌표.
    int chk = a[y][x];
    for(int i = y ; i < y + size; i++){
        for(int j= x; j < x + size; j++){
            if(chk == 0 && a[i][j] == 1) chk = 2;
            else if (chk == 1 && a[i][j] == 0) chk = 2;

            if(chk == 2){
                count(y, x, size/2);
                count(y, x + size/2, size / 2);
                count(y + size / 2, x, size / 2);
                count(y + size/2, x + size/2, size/2);
                return;
            }
        }
    }
    if(chk == 0) white_cnt++;
    else blue_cnt++;
}

            if(chk == 2){
                count(y, x, size/2);
                count(y, x + size/2, size / 2);
                count(y + size / 2, x, size / 2);
                count(y + size/2, x + size/2, size/2);
                return;
            }

이 부분이 이 문제의 핵심이라고 볼 수 있다.

개념을 확실히 하려고 비슷한 문제를 하나 더 풀었다. 사실상 거의 같은 문제다.

https://www.acmicpc.net/problem/1780
1780 종이의 개수

#include <iostream>
#include <algorithm>

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

int n;
int a[2200][2200];
int minus_cnt, zero_cnt, plus_cnt;

void solve();
void count(int y, int x, int size);

int main(){
    fastio;
    solve();
    return 0;
}

void solve(){
    cin >> n;
    for(int i = 0 ; i < n; i++)
        for(int j = 0 ; j < n; j++)
            cin >> a[i][j];


    count(0, 0, n);
    cout << minus_cnt << '\n' << zero_cnt << '\n' << plus_cnt << '\n';
}

void count(int y, int x, int size){

    int std = a[y][x];
    int chk = std;
    for(int i = y ; i < y + size; i++){
        for(int j = x ; j < x + size ; j++){
            if(a[i][j] != std){
                count(y, x, size/3);
                count(y, x + size/3, size/3);
                count(y, x + size*2/3, size/3);

                count(y + size/3, x, size/3);
                count(y + size/3, x + size/3, size/3);
                count(y + size/3, x + size*2/3, size/3);

                count(y + size*2/3, x, size/3);
                count(y + size*2/3, x + size/3, size/3);
                count(y + size*2/3, x + size*2/3, size/3);
                return;
            }
        }
    }
    if(chk == -1) minus_cnt++;
    else if(chk == 0) zero_cnt++;
    else plus_cnt++;
}