[백준 C++] 2630 색종이 만들기 - 분할정복

2630번: 색종이 만들기

#include <iostream>
using namespace std;

int Paper[128][128];
int CountWhite;
int CountBlue;

void DividePaper(int StartRow, int StartCol, int Size)
{
	bool bDivide = false;
	int ColorCheck = -1;

	for (int i = StartRow; i < StartRow + Size; ++i)
	{
		for (int j = StartCol; j < StartCol + Size; ++j)
		{
			if ((ColorCheck == 0 && Paper[i][j] == 1)
				||
				(ColorCheck == 1 && Paper[i][j] == 0))
			{
				bDivide = true;
				break;
			}

			ColorCheck = Paper[i][j];
		}

		if (bDivide)
		{
			break;
		}
	}

	if (bDivide)
	{
		DividePaper(StartRow, StartCol, Size / 2);
		DividePaper(StartRow + Size / 2, StartCol, Size / 2);
		DividePaper(StartRow, StartCol + Size / 2, Size / 2);
		DividePaper(StartRow + Size / 2, StartCol + Size / 2, Size / 2);
	}
	else
	{
		if (ColorCheck == 0)
		{
			++CountWhite;
		}
		else if (ColorCheck == 1)
		{
			++CountBlue;
		}
	}
}

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

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

	DividePaper(0, 0, N);

	cout << CountWhite << '\n';
	cout << CountBlue << '\n';
}

---

 

재귀 함수를 이용해서 푸는 분할 정복 유형의 문제입니다.

주어진 범위 내에서 색이 모두 같다면 해당 색을 카운트 +1 해주고

색이 모두 같지 않다면 4등분 하도록 해서 풀었습니다.

모든 재귀함수가 수행된 후에 각각 카운트한 색상의 수를 출력하도록 했습니다.