BOJ 2630 색종이 만들기

이 문제는 N*N 크기의 종이를 모든 부분이 같은 색으로 칠해져 있을때 까지 N/2*N/2로 계속 나누면서 각각 1을 파란색, 0을 하얀색으로 나타내고 이때 파란색 색종이와 하얀색 색종이의 갯수를 각각 출력하는 문제이다. 

 

풀이 방법은 재귀를 이용한 방법이다. 전체 종이 길이 N에 대해서 재귀를 반복할 때마다 색종이의 한변 길이를 N/2 씩 줄여나가면서 1사분면,2사분면,3사분면,4사분면으로 분할하여 탐색하면 된다. 

 

이렇게 분할 하였을때 가장 중요한 부분은 범위이다. (1,1)을 기준으로 모든 사분면의 범위를 구하는 방법은 다음과 같다.

1사분면 : (1,1) / 2사분면 : (1,1+N/2) / 3사분면 : (1+N/2,1) / 4사분면 : (1+N/2,1+N/2) 이 되고 이를 일반화 하면

1사분면 : (x,y) / 2사분면 : (x,y+N/2) / 3사분면 : (x+N/2,y) / 4사분면 : (x+N/2,y+N/2) 가 된다.

 

이를 바탕으로 작성한 코드는 다음과 같다.

#include<iostream>
#include<cstring>
using namespace std;

int n;
int arr[130][130];
int blueCnt = 0, whiteCnt = 0;

void solution(int x, int y, int size)
{
	bool blue = false;
	bool white = false;
	for(int i = 0; i < size; i++)
	{
		for(int j = 0; j < size; j++)
		{
			if(arr[x + i][y + j] == 1)
			{
				blue = true;
			}
			if(arr[x + i][y + j] == 0)
			{
				white = true;
			}
		}
	}

	if(blue && white)
	{
		int newSize = size >> 1;
		if(newSize == 0)
		{
			return;
		}
		solution(x, y, newSize);
		solution(x, y + newSize, newSize);
		solution(x + newSize, y, newSize);
		solution(x + newSize, y + newSize, newSize);
	}
	else if(blue)
	{
		blueCnt++;
	}
	else if(white)
	{
		whiteCnt++;
	}
}

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

	memset(arr, -1, sizeof(arr));

	cin >> n;

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

	solution(1, 1, n);

	cout << whiteCnt << "\n" << blueCnt;

}