BOJ 2630번 :: 색종이 만들기

#문제

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

2630번: 색종이 만들기

 

#작성 코드

#include <iostream>
using namespace std;
 
int n;
bool paper[129][129];    // 인덱스 1~128을 사용한다. 
int white=0, blue=0;
int d[4][2] = {{0,0}, {0,1}, {1,0}, {1,1}}; 
 
bool sameColor(int x, int y, int size){
    // (x,y)에서 시작하는 size*size가 모두 같은 색으로 칠해져있는지 체크 
    bool start = paper[x][y];
    bool flag = true;
    // (1,1)에서 시작해서 size가 8인경우, 1,..., 1+8-1까지. 
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
             if( start != paper[i][j] )
                 flag = false;
        }
    }
    
    // 모든 색이 같다면 
    if( flag ){
        if(start==0)    // 그 색이 흰색이라면 흰 색종이+1 
            white++;
        else            // 그 색이 파란색이라면 파란 색종이+1 
            blue++;
    }
    // 모든 색이 같지 않다면 
    if( !flag ){
        // 4등분해서 같은 색인지 각각 또 비교한다. 
        for(int i=0; i<4; i++){
            sameColor(x+d[i][0]*size/2, y+d[i][1]*size/2, size/2);
        }
    }
    return flag;
}
 
void input(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>paper[i][j];
        }
    }
}
 
int main(){
    input();
    sameColor(1, 1, n);
    cout<<white<<'\n'<<blue<<'\n';
    return 0;
}

##

sameColor(x, y, size)는 (x,y)에서부터 size*size 크기의 색종이가 모두 같은 색으로 이루어져있는지 판단한다.

모두 같은 색인지는 flag에 저장한다. 같은 색이라면 true, 같은 색이 아니라면 false가 저장된다.

 

만약 flag가 true라면

    모두 같은 색이므로 (x,y)가 무슨 색인지 보고, 그에 해당하는 색종이 조각의 개수를 하나 늘린다.

만약 flag가 false라면

    그 색종이를 가로, 세로로 2등분씩 총 4등분하여 각 조각을 sameColor로 또 비교한다.

    -> sameColor(x, y, size/2)

    -> sameColor(x+size/2, y, size/2)

    -> sameColor(x, y+size/2, size/2)

    -> sameColor(x+size/2, y+size/2, size/2)