[백준]Baekjoon1780(분할 정복)

문제링크 : https://www.acmicpc.net/problem/1780

분할 정복을 통해 풀 수 있는 문제이다.

따로 2개의 함수를 정의했는데 하나는 모든 수가 같은지 체크하는것, 

또 다른 하나는 분할정복을 가능하게 하는 함수이다.

모든 수가 같은지 체크하는 것은 그냥 주어진 종이를 둘러보며 하나라도 숫자가 다르면

false를 return하고 모두 같다면 true를 return 하도록 하였다.

중요한것은 분할 정복을 가능하게 만드는 함수이다.

인자로 가장 맨 왼쪽 위의 점과 종이의 길이를 주었다.

먼저 그 함수에 들어가면 종이 안의 모든 숫자가 같은지 check를 한 다음에 

만약 같다면 어떤 숫자인지 확인해서 결과값을 조정하였고

만약 숫자가 같지 않다면 그 종이를 9등분으로 짤라서 같은 과정을 다시 수행해야하기 때문에

if (!check(x, y, len)) {

for (int i = x; i < x + len; i += (len / 3)) {

for (int j = y; j < y + len; j += (len / 3)) {

solve(i, j, len / 3);

}

}

}

이런식으로 다시 9등분된 종이에 대해 함수를 다시 수행하도록 하였다.

#include <iostream>
#include <queue>

using namespace std;

int arr[4000][4000]; //행렬 초기화
int answer[3]; //종이의 갯수

bool check(int x, int y, int len) {
	bool b = true;
	int num = arr[x][y];
	for (int i = x; i < x + len; i++) {
		for (int j = y; j < y + len; j++) {
			if (num != arr[i][j])
				return false;
		}
	}
	return true;
}
void solve(int x, int y, int len)
{
	if (!check(x, y, len)) {
		for (int i = x; i < x + len; i += (len / 3)) {
			for (int j = y; j < y + len; j += (len / 3)) {
				solve(i, j, len / 3);
			}
		}
	}
	else if(len == 1 || check(x,y,len)){
			answer[++arr[x][y]]++;
	}
}
int main()
{
	int N;
	scanf("%d", &N);
	answer[0] = 0; answer[1] = 0; answer[2] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	solve(0, 0, N);
	
	for (auto x : answer)
		printf("%d\n", x);

}