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

문제: www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

문제풀이

 

주어진 종이가 같은 색으로 모두 칠해져 있을 때까지 종이를 4 등분한다.

 

재귀를 이용하여 종이가 같은 색으로 칠해져 있을 때까지 함수를 반복했다.

 

함수에서 기준점의 인덱스와 종이의 크기를 매개변수로 넘겨주었다.

 

 

코드

#include <iostream>

using namespace std;

int arr[129][129] = {0}; //종이의 크기는 최대 128x128
int bcnt=0; //파란색(1) 종이 조각의 개수
int wcnt=0; //하얀색(0) 종이 조각의 개수

void func(int x, int y, int N){
    bool flag = true;

    for(int i=x; i<x+N; i++){
        for(int j=y; j<y+N; j++){
            if(arr[x][y] != arr[i][j]){ //종이가 같은 색으로 채워져있지 않다면
                flag = false;
                break;
            }
        }
    }

    if(flag && arr[x][y] == 0){ //모두 0으로 채워져있다면
        wcnt++;
    }
    else if(flag && arr[x][y] == 1){ //모두 1로 채워져있다면
        bcnt++;
    }
    else{ //4등분
        func(x, y, N/2);
        func(x, y+N/2, N/2);
        func(x+N/2, y, N/2);
        func(x+N/2, y+N/2, N/2);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>arr[i][j];
        }
    }

    func(0,0,N);

    cout<<wcnt<<"\n"<<bcnt;

    return 0;
}

 

 

결과