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

[문제]

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

2630번: 색종이 만들기

[문제 풀이]

분할정복을 해야 한다는 것은 쉽게 예측이 되지만 막상 구현을 할려고 하니 어떻게 해야할지 많이 헤맸던 문제이다.

기본적으로 가로, 세로의 길이가 n인 색종이를 접는다고 생각하면 쉽게 접근이 가능하다.

색종이를 접을때 자기 자신을 다시 한번 방문해야 한다는 것을 생각하자.

문제의 핵심은 이동하고 있는 위치에서 다시 한번 실행하는것이 아니라 맨 처음 실행했던 곳과 거기서부터 색종이를 4등분해서 두번 접은 곳으로 보내는 것이다.

 

현재 위치의 색깔을 체크해주자.(10)

자신의 위치부터 size 만큼 더한 값을 돌아주자.(12~13)

만일 현재 색깔과 다른 부분이 나왔다면 체크를 바꿔주자.(14~15)

만일 체크가 blue도 white도 아닌 색깔이라면(17)

처음 자신의 위치와 y를 사이즈의 절반만큼 더한 곳, x를 사이즈의 절반만큼 더한 곳, y와 x를 사이즈의 절반만큼 더한 곳으로 보내주자.(18~21)

색종이를 접었다면 현재 함수를 종료해주자(22)

만일 색종이를 접을동안 문제가 없었다면 현재 색깔을 1번 더해주자.(26~31)

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
int confetti[130][130];
int blue,white;
 
void fold(int x, int y, int size){
    int check = confetti[x][y];
    
    for(int i = x;i< x+size;i++){
        for(int j = y;j<y+size;j++){
            if(confetti[i][j] != check){
                check = 2;
            }
            if(check == 2){
                fold(x, y, size / 2);
                fold(x, y + size/2, size /2 );
                fold(x + size / 2, y , size / 2);
                fold(x + size / 2, y + size / 2, size / 2);
                return;
            }
        }
    }
    if( check == 0){
        white++;
    }
    else{
        blue++;
    }
    return;
}
 
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>confetti[i][j];
        }
    }
 
    fold(0,0,n);
 
    cout<<white<<endl;
    cout<<blue<<endl;
 
    return 0;
}