[백준] 2630 색종이 만들기 (C++)

 

문제 URL:

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

2630번: 색종이 만들기

 

다음 문제는 크기가 N×N인 종이를 규칙대로 잘랐을 때

만들어지는 하얀색과 파란색 종이의 개수를 출력하는 문제로,

분할정복을 이용하여 푸는 문제였다. 

 

현재 위치의 좌표 색상을 current로 설정하고 현재 좌표가 속해 있는 사분면을 탐색하는데

이때, 다른 색상이 존재한다면 current를 -1로 설정하여 다시 사분면을 탐색한다. 

다른 색상이 존재하지 않는다면 current 값에 따라서 white나 blue를 증가시켜 준다. 

---

#include <iostream>
using namespace std;

int n;
int map[128][128];
int blue, white;  //  1, 0

void check(int y, int x, int size) {
	int current = map[y][x];  // 현재 좌표의 색상

	// 현재 좌표가 속해 있는 사분면 탐색
	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (current == 0 && map[i][j] == 1)
				current = -1;
			else if (current == 1 && map[i][j] == 0)
				current = -1;

			// 종이를 나눈 뒤 다시 제2/1/3/4 사분면 탐색
			if (current == -1) {
				check(y, x, size / 2);
				check(y, x + size / 2, size / 2);
				check(y + size / 2, x, size / 2);
				check(y + size / 2, x + size / 2, size / 2);
				return;
			}
		}
	}
	if (current == 0)
		white++;
	else
		blue++;
}

int main() {
	cin >> n;

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

	check(0, 0, n);

	cout << white << '\n';
	cout << blue << '\n';

	return 0;
}