백준 2630 색종이 만들기 c++ [컴공과고씨]

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

2630번: 색종이 만들기

 

문제 간단 정리

NxN의 모눈 색종이가 있을때 각 칸에 1 또는 0이 적혀있음.

모든 숫자가 같아 정사각형이 되지 않으면 4등분하여 색종이를 나누어가면서 정사각형이 될 때 까지 나누었을 때

잘려진 흰색 종이와 파란색 종이의 개수를 구하시오.

*이 문제는 본문에 있는 그림을 보면 더 쉽게 이해가능.

 

문제 해결 방법

분할 정복(divide and conquer), 재귀를 써서 간단히 풀 수 있다.

먼저 색종이를 보고 값을 체크하며 하나로 이루어져있는지 아닌지를 판단함.

만약 중간에 다른 값이 섞여 있다면 잘라야하는 파트임.

 

값을 자를 때 한번 자를 때 마다 변의 길이는 1/2이 된다.

예를 들어 n = 8 이면 처음에는 8 그 파트는 4 그 다음은 2 이런식으로 갈 것이다.

이것을 이용해서 파트를 나누었을 때 우리는 4등분을 하고 그것들을 다시 함수에 넣어 색종이를 잘라야하는지

판단하는 것을 반복해준다.

여기서 4등분이란 이런식으로 위쪽에 왼쪽 파트, 위쪽에 오른쪽 파트, 아래쪽에 왼쪽 파트, 아래쪽에 오른쪽 파트로 구성이 되며 이것들을 다시 함수에 넣어 더 잘라야하는지 보는 것이다.

 

만약 더 이상 자를 필요가 없는 파트는 무슨 색인지 확인 후 색깔 별 총 개수에 +1 해주면 된다.

이 정도로 하고 전체 코드를 보면 더욱 이해가 쉬울 것이다.

 

전체 코드

#include <iostream>
using namespace std;
int arr[129][129]; 
int white = 0; // 흰 종이
int blue = 0; // 파란 종이
void fc(int x, int y, int k){
    bool cut = false; // 잘라야하는지 
    int first_color = arr[x][y]; // 첫번째칸의 색
    for (int i = x; i < x + k;i++){
        for (int j = y; j < y + k;j++){
            if(arr[i][j] != first_color){ // 중간에 다른색이 나오면
                cut = true; // 잘라야함.
                break; 
            }
        }
    }
    if(cut){ // 잘라야하는 색종이면 
        fc(x, y, k / 2); // 위쪽에 왼쪽 파트
        fc(x, y + k / 2, k / 2); //위쪽에 오른쪽 파트
        fc(x + k / 2, y, k / 2); // 아래쪽에 왼쪽 파트
        fc(x + k / 2, y + k / 2, k / 2); // 아래쪽에 오른쪽 파트
    }else{
        if(first_color == 1) // 파란색
            blue++;
        else // 흰색
            white++;
    }    
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            cin >> arr[i][j];
        }
    }
    fc(0, 0, n);
    cout << white << '\n';
    cout << blue << '\n';
    return 0;
}