BOJ [1780] 종이의 개수

https://www.acmicpc.net/problem/1780

1. 분류

분할정복

2. 풀이

대놓고 분할정복으로 풀라는 문제이다.

3의 제곱으로 입력이 주어진 입력을 계속 9등분하여 영역을 구해야 한다.

중앙부터 시작하여 조건이 충족되었는지 검사하고, 9등분으로 나뉜 각 영역의 중앙으로 이동하여 다시 검사한다.

재귀함수와 각 영역을 검사하는 함수를 만들었다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

1. 재귀함수는 위의 두 가지 조건을 충족시켜야 한다. 

 1의 조건이 만족하지 않는 영역을 분할하며 각 영역의 중앙을 매개변수로 다시 재귀함수를 실행한다.

 한 번 재귀함수를 호출할 때마다 n을 3등분시켰고 n이 0이면 기저조건으로 바로 함수를 종료한다.

2. 영역을 검사하는 함수는 bool형으로 만들어 영역의 모든 원소를 검사한다.

 반복문 실행 횟수를 정해주기 위해 n값을 넣어주었다.

3. 소스코드

#include <cstdio>

int paper[2200][2200];
int cnt[3];

bool chkPaper(int x, int y, int n)
{
	int target = paper[y][x];

	for (int i = y; i < y + n; i++)
		for (int j = x; j < x + n; j++)
			if (paper[i][j] != target)
				return false;

	cnt[target + 1]++;
	return true;
}

void recur(int x, int y, int n)
{
	if (!n)
		return;

	if (!chkPaper(x - n/2, y - n/2, n))
		for (int i = -1; i <= 1; i++)
			for (int j = -1; j <= 1; j++)
				recur(x - (n / 3) * j, y - (n / 3) * i, n / 3);

	return;
}

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			scanf("%d", &paper[i][j]);
	}

	recur(n / 2, n / 2, n);

	printf("%d\n%d\n%d\n", cnt[0], cnt[1], cnt[2]);

	return 0;
}