분할정복 - 백준 2630번 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

IDEA 

계속 4등분으로 쪼개주면 된다. 

쪼갠 후 그 네모난 영역에 대해서 이중 for문을 통해 다 한 숫자(0 혹은 1)로 이뤄져있는지 확인해준다.

0이면 white 를 카운트해주고 1이면 blue 를 카운트해준다. 

전체 영역의 개수 $n^{2}$과 white /blue 중 하나가 같다면 한 숫자로만 이루어져있다는 뜻이다. 

한 숫자로 이루어져있다면 더이상 쪼개지 않고 return 해버린다.

만약 한 숫자로만 이루어져있지 않다면 또 4등분을 하며 1x1이 될 때까지 쪼개준다. 

 

CODE

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int arr[130][130] , blue_cnt = 0 , white_cnt = 0;

void divide(int start_row, int start_col , int n ){
	int blue=0, white=0;
	for (int i = start_row; i < start_row + n; i++) {
		for (int j = start_col; j < start_col + n; j++) {
			arr[i][j] == 1 ? blue++ : white++;
		}
	}
	if (blue == n * n ) //모두 한 색깔로 채워져있는 경우
	{
		blue_cnt++;
		return;
	}
	else if (white == n * n) {
		white_cnt++;
		return;
	}
	else {
		divide(start_row, start_col, n / 2);
		divide(start_row + n/2, start_col, n / 2);
		divide(start_row, start_col + n/2, n / 2);
		divide(start_row + n/2, start_col + n/2, n / 2);
	}
}


int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	divide(0, 0, n); 
	printf("%d\n%d", white_cnt , blue_cnt);
}