#2630번 색종이 만들기 (C++)

링크 : www.acmicpc.net/problem/2630

2630번: 색종이 만들기

재귀를 통해 풀었으며, 얼핏보면 DFS와 비슷한 원리의 문제이다.

분할정복으로 분류되어있는데, 문제에서 언급되었듯이 정확히 반씩 탐색하면 되는 문제이므로

그리 복잡한 원리를 요구하지 않는다. 

 

문제풀이는 다음과 같다.

1. 재귀를 통해 1번째 배열부터 마지막번호까지 재귀함수를 진행한다. 

2. 만약 지정된 범위의 타일을 모두 세었을 때, 하얀 타일이나 파란 타일의 갯수가 0개라면 

색종이가 완성된다.

3. 그렇지 않을 경우에 아래와 같이 네 분할로 나누어 다시 재귀를 진행한다. 

1사분면	2사분면
3사분면	4사분면

#include <iostream>
using namespace std;

int n = 0, arr[129][129], wh = 0, bl = 0;

void check(int starty, int startx, int endy, int endx) {
	int white = 0, blue = 0;
	for (int i = starty; i <= endy; i++) {
		for (int j = startx; j <= endx; j++) {
			if (arr[i][j] == 0) white++;
			else blue++;
		}
	}
	if (blue == 0||white==0) {
		if (blue == 0) wh++;
		else bl++;
	}
	else {
		check(starty, startx, (starty+endy) / 2, (startx+endx) / 2); // 1사분면
		check(starty, (startx+endx)/2+1,(starty+endy)/2,endx); // 2사분면
		check((starty+endy)/2+1, startx, endy, (startx+endx)/2); // 3사분면
		check((starty + endy) / 2 + 1, (startx + endx) / 2 + 1, endy, endx); //4사분면
	}
}

int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) cin >> arr[i][j];
	}
	check(1, 1, n, n);
	cout << wh << "\n" << bl << "\n";
	return 0;
}