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

 

풀이

문제를 보면 알 수 있듯이 분할정복 관련 문제이다.

#include <iostream>

using namespace std;

#define MAX 128

int n;
int cntWhite = 0, cntBlue = 0;
int map[MAX][MAX];

void DevideAndConquer(int x, int y, int size) {
	int color = map[x][y];

	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (color != map[i][j]){
				DevideAndConquer(x, y, size / 2);
				DevideAndConquer(x, y + size / 2, size / 2);
				DevideAndConquer(x + size / 2, y, size / 2);
				DevideAndConquer(x + size / 2, y + size / 2, size / 2);

				return;
			}
		}
	}
	if (color)
		cntBlue++;
	else
		cntWhite++;
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	DevideAndConquer(0, 0, n);
	cout << cntWhite << "\n" << cntBlue;

	return 0;
}