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

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

---

 문제 풀이

분할 정복의 첫 문제이다.

함수 div_conq에 x와 y의 좌표를 넣어서 내부에 파란색이 하나라도 칠해져 있다면 4등분으로 나눈다.

함수에서 따지는 cnt의 개수가 0이라면 지금 확인하는 영역이 파란색으로 칠한 것이 하나도 없는 경우이다.

반대로 cnt의 개수가 변의 길이의 제곱과 같다면 확인하는 영역이 모두 파란색이라는 것이다.

그 외에 개수가 애매하다면 4등분으로 나누어서 따지면 된다.

 느낀 점

분할 정복의 첫 문제이고 막 그림이 나와서 되게 어렵게 생각했다. 하지만 천천히 따지고 보니 이전에 공부했던 merge sort의 기본 개념과 많이 유사해 보인다. 새로운 국면을 마주쳤는데 생각보다 재밌어서 재밌게 공부할 수 있을 것 같다.

 코드

#include <iostream>

using namespace std;

int n;
int arr[129][129];
int cnt_w = 0, cnt_b = 0;

void div_conq(int x, int y, int n) {
	int cnt = 0;
	for (int i = x; i < x + n;i++) {
		for (int j = y; j < y + n;j++) {
			if (arr[i][j]) {
				cnt++;
			}
		}
	}
	if (!cnt) cnt_w++;
	else if (cnt == n * n) cnt_b++;
	else {
		div_conq(x, y, n / 2);
		div_conq(x+ n / 2, y, n / 2);
		div_conq(x, y + n / 2, n / 2);
		div_conq(x + n / 2, y + n / 2, n / 2);
	}
	return;
}

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

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

	div_conq(0, 0, n);
	cout << cnt_w << "\n" << cnt_b;
}