[2630] 색종이 만들기

---

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

2630번: 색종이 만들기

분할 정복, 재귀 문제이다.

 

만든 정사각형 안이 모두 같은 색이 될 때까지 쪼개야한다. 0이면 흰색, 1이면 파란색을 뜻한다.

 

그래서 정해진 구간에서 모두 같은 색을 갖고있는지 판별한 후, 

다른 색이 있다면 더 쪼개고(분할), 같은 색이라면 흰색인지 파란색인지 판별하여 count해준다.

 

 

작은 정사각형으로 쪼갤 때 총 4개의 정사각형이 새로 생긴다.

그래서 그림을 참고하여 1구간, 2구간, 3구간, 4구간으로 쪼개주었다.

쪼갠 정사각형 구간 한 변의 길이는 모두 N/2인 것을 볼 수 있다.

 

 

그렇게 완성된 코드이다.

#include <iostream>
using namespace std;

// 0 : white, 1 : blue

int N; int A[129][129];
int white, blue;

void cut(int x, int y, int n) {
	int color = A[x][y]; // 이 구간의 color를 구함
	bool diff = false;

	// 정해진 구간에서 모두 같은 색인지 판별
	for (int i = x; i <= x + n-1; i++) {
		for (int j = y; j <= y + n-1; j++) {
			if (color != A[i][j]) { // 색이 다르다면 
				diff = true; // 빠져나오기
				break;
			}
		}
		if (diff) break;
	}

	if (diff) { // 색이 구간 안에서 다르다면
		// 더 쪼개기
		cut(x, y, n / 2); // 1구간 (왼쪽 위)
		cut(x + n / 2, y, n / 2); // 2구간 (오른쪽 위)
		cut(x, y + n / 2, n / 2); // 3구간 (왼쪽 아래)
		cut(x + n / 2, y + n / 2, n / 2); // 4구간 (오른쪽 아래)
	}
	else {
		if (color == 0) white++;
		else blue++;
	}
}


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

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> A[i][j];
		}
	}

	cut(1, 1, N);

	printf("%d\n%d", white, blue);
}