[백준 2630] 색종이 만들기

이분탐색 풀다 완탐 풀고 싶어서 오랜만에 완탐 문제 풀어봄

 

그냥 한 정사각형 색종이가 만들어질때까지만 재귀를 돌려주면 된다

 

---

#include <iostream>

using namespace std;

int** board;
int white, blue;

bool check(int starty, int startx, int size) {
	int flag;
	if (board[starty][startx] == 1) flag = 1; // blue
	else flag = 0; // white

	for (int y = starty; y < starty + size; y++) {
		for (int x = startx; x < startx + size; x++) {
			// 파란색인데 흰색 나오거나
			if (flag && board[y][x] == 0) return false;
			// 흰색인데 파란색나오면
			if (!flag && board[y][x] == 1) return false;
		}
	}

	if (flag) blue++;
	else white++;

	return true;
}

void solve(int starty, int startx, int size) {

	// 다 같은 수로 채워져있으면
	if (check(starty, startx, size)) return;

	int newsize = size / 2;
	solve(starty, startx, newsize);
	solve(starty + newsize, startx, newsize);
	solve(starty, startx + newsize, newsize);
	solve(starty + newsize, startx + newsize, newsize);

	return;
}

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

	int N; cin >> N;
	
	board = new int*[N];
	for (int i = 0; i < N; i++) {
		board[i] = new int[N];
	}

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

	solve(0, 0, N);

	cout << white << "\n";
	cout << blue;

	return 0;
}