[분할 정복 단계] 백준 1780번 종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

기존 분할 정복에서 3 x 3 9개로 분리하는 범위만 잘 나누어주면 된다.

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;


int arr[2187][2187];
int minusc;
int zeroc;
int onec;

void check(int y, int x, int N)
{
	bool fminus = true;
	for (int i = y; i < y + N; i++)
	{
		for (int j = x; j < x + N; j++)
		{
			if (arr[i][j] != -1)
			{
				fminus = false;
				break;
			}
		}
	}


	bool fone = true;
	for (int i = y; i < y + N; i++)
	{
		for (int j = x; j < x + N; j++)
		{
			if (arr[i][j] != 1)
			{
				fone = false;
				break;
			}
		}
	}

	bool fzero = true;
	for (int i = y; i < y + N; i++)
	{
		for (int j = x; j < x + N; j++)
		{
			if (arr[i][j] != 0)
			{
				fzero = false;
				break;
			}
		}
	}

	if (fone || fzero || fminus)
	{
		if (fone)
		{
			onec++;
		}
		if (fzero)
		{
			zeroc++;
		}

		if (fminus)
		{
			minusc++;
		}	
		return;
	}

	check(y, x, N / 3);
	check(y, x + N / 3, N / 3);
	check(y, x + (N / 3) * 2, N / 3);
	check(y + N / 3, x, N / 3);
	check(y + N / 3, x + N / 3, N / 3);
	check(y + N / 3, x + (N / 3) * 2, N / 3);
	check(y + (N / 3) * 2, x, N / 3);
	check(y + (N / 3) * 2, x + N / 3, N / 3);
	check(y + (N / 3) * 2, x + (N / 3) * 2, N / 3);
}


int main() {

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

	check(0,0,N);
	cout << minusc << endl;
	cout << zeroc << endl;
	cout << onec << endl;
}