[BOJ]2630-색종이 만들기

2630

분할 정복 리마인드 문제!

성공코드

#include <iostream>
using namespace std;

int arr[130][130];

int N;
int whiteBox = 0;
int blueBox = 0;

void search(int x, int y, int length)
{
	bool flag = false;
	int std = arr[x][y];

	for (int i = x; i < x + length; i++)
	{
		for (int j = y; j < y + length; j++)
		{
			if (arr[i][j] != std)
			{
				flag = true;
				break;
			}
		}

		if (flag)
		{
			break;
		}
	}

	if (flag)
	{
		int size = length / 2;

		search(x, y, size);
		search(x, y + size, size);
		search(x + size, y, size);
		search(x + size, y + size, size);
	}
	else
	{
		if (std == 0)
		{
			whiteBox += 1;
		}
		else
		{
			blueBox += 1;
		}
	}

}

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

	cin >> N;

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

	search(0, 0, N);

	cout << whiteBox << '\n' << blueBox;
}