BOJ 1780 (종이의 개수)

• 문제
  N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
  
  만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
  (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
  이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
  
  
• 출력
  첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

#include<iostream>
#define MAX 2188
using namespace std;

int p[MAX][MAX];
int One_count, Zero_count, MOne_count = 0;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

void cut_off(int x, int y, int num)
{
	bool One = true, MOne = true, Zero = true;
	for (int i = y; i < y + num; i++)
	{
		for (int j = x; j < x + num; j++)
		{
			if (p[i][j] == -1)
			{
				Zero = false;
				One = false;
			}
			if (p[i][j] == 0)
			{
				One = false;
				MOne = false;
			}
			if (p[i][j] == 1)
			{
				Zero = false;
				MOne = false;
			}
		}
	}
	if (MOne) { MOne_count++; return; }
	if (Zero) { Zero_count++; return; }
	if (One) { One_count++; return; }
	cut_off(x, y, num / 3);
	cut_off(x, y + num / 3, num / 3);
	cut_off(x, y + (num / 3) * 2, num / 3);
	cut_off(x + num / 3, y, num / 3);
	cut_off(x + (num / 3) * 2, y, num / 3);
	cut_off(x + num / 3, y + num / 3, num / 3);
	cut_off(x + (num / 3) * 2, y + num / 3, num / 3);
	cut_off(x + num / 3, y + (num / 3) * 2, num / 3);
	cut_off(x + (num / 3) * 2, y + (num / 3) * 2, num / 3);
}

int main()
{
	void fast_io();
	int N; cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> p[i][j];
		}
	}
	cut_off(0, 0, N);
	cout << MOne_count << '\n' << Zero_count << '\n' << One_count;
}

앞에서 풀었던 색종이 만들기 문제와 유사한 divide & conquer과 재귀로 해결하는 문제이다
앞에서는 4등분 했기 때문에 재귀가 4번 돌아갔지만 위 문제는 9등분을 하기 때문에 재귀 함수 9번을 호출해 주었다. (문제 푸는 방식은 유사)

* 위와 같은 문제가 나온다면 이 방식으로 풀면 될 것 같다.