백준 - 2630번 : 색종이 만들기 (C++)

풀이 방법 : 재귀 탐색

가능한 최대 크기의 정사각형부터 체크하여 한 가지 색깔로 이뤄진 정사각형인 경우 해당 색깔의 수를 늘려주고 정사각형이 아닌 경우, 영역을 1/4로 나눠 각 사각형을 반복적으로 체크해준다.
이를 위해 색깔 체크 함수를 재귀 호출 해주었다.

#include <iostream>

using namespace std;

bool Color[128][128] = {};
int DirX[4] = { 1,0,1,0 };
int DirY[4] = { 1,1,0,0 };

int BlueCnt = 0;
int WhiteCnt = 0;

void CheckSquare(int y, int x, int Size)
{
	int StartColor = Color[y][x];
	bool Enable = true;

	for (int i = 1; i < Size; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (Color[y + i][x + j] != StartColor)
			{
				Enable = false;
				break;
			}
		}

		for (int j = 0; j <= i; ++j)
		{
			if (Color[y + j][x + i] != StartColor)
			{
				Enable = false;
				break;
			}
		}

		if (!Enable)
			break;
	}
	
    //한 가지 색깔로 이뤄지지 않은 경우
	if (!Enable)
	{
    	//네 가지 영역으로 나눠 재귀호출
		for (int i = 0; i < 4; ++i)
		{
			int NextY = y + (Size / 2) * DirY[i];
			int NextX = x + (Size / 2) * DirX[i];

			CheckSquare(NextY, NextX, Size / 2);
		}
	}

	else
	{
		if (StartColor == 1)
			++BlueCnt;

		else
			++WhiteCnt;
	}
}

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

	int N;
	cin >> N;

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

	CheckSquare(0, 0, N);
	
	cout << WhiteCnt << '\n';
	cout << BlueCnt << '\n';

}