[알고리즘] 백준 2630번: 색종이 만들기 (C++), 분할 정복 드디어

이번 문제는 첫 공식적인(?) 분할 정복 문제다.

의외로 간단하게 풀었었다. '다만 생각을 조금만 더 해볼 걸'이라는 아쉬움이 있었다.

'설마 하나하나 다 검사하겠어'라는 생각에 한 번이라도 구현했으면 시간 아꼈을 텐데

---

포인트

이번 분할 정복의 포인트는 문제에서 얻을 수 있었다. n이 2의 제곱수로 주어지고, 색종이들 또한 2의 제곱수 형태로 존재하기 때문에 N / 2로 분할해나가면서 리커시브 콜을 하면 됐었다.

맨 위에서 말한 '설마 하나하나 다 검사하겠어'라는 생각을 구현하면 된다.

---

소스 코드

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

int n;
int map[129][129] = { 0, };

int white = 0; // 0
int blue = 0; // 1

void divideAndQonquer(int col, int row, int n) {
	int check = 0; // 1이 하나라도 나온다면 분할해야 함 혹은 0 -> 0색종이 cnt++ || n * n -> 1색종이 cnt++
	// 이 반복문으로 색종이 check
	for (int i = col; i < col + n; i++) {
		for (int j = row; j < row + n; j++) {
			if (map[i][j] == 1) {
				check++;
			}
		}
	}

	if (check == 0) {
		white++;
	}
	else if (check == n * n) {
		blue++;
	}
	else {
		divideAndQonquer(col + n / 2, row, n / 2); // 1사분면
		divideAndQonquer(col, row, n / 2); // 2사분면
		divideAndQonquer(col, row + n / 2, n / 2); // 3사분면
		divideAndQonquer(col + n / 2, row + n / 2, n / 2); // 4사분면
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}

	divideAndQonquer(1, 1, n);
	cout << white << '\n' << blue;
	return 0;
}

분할 정복 함수에서 check를 통해 반복문을 돌면서 이것이 혼합되어있는 종이인가 단색 종이인지를 파악한다. 이것이 1번째 포인트, 이걸 어떻게 분할할 것인지가 두 번째 포인트였다.

---

아직은

아직은 분할 정복 문제를 더 풀어보면서 감을 익혀야 한다. 이번 문제는 꽤나 직관적으로 이렇게 하라는 듯이 주어졌던 문제라 더 어려운 문제들을 보면서 분할 정복을 떠올릴 수 있게 해야 한다.