[C++] 백준 1780번 종이의 개수

분할정복 문제입니다.

사각형에서 모든 숫자가 같으면 그 숫자에 대해서 카운트를 증가합니다.
다를 경우에 사각형을 9조각으로 나누어서 위의 작업을 반복합니다.
최종적으로 -1, 0, 1이 총 몇개의 사각형으로 이루어져있는지 출력합니다.

시작점 위치의 값을 check에 넣고 반복문을 통해서 다른 값들과 비교합니다.
다를경우 check=2로 바꾸고 9조각으로 나눠서 작업을 반복합니다.
같을 경우 check의 값에 따라 해당하는 카운트를 증가시켜줍니다.

 

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

int c[3];
int map[3000][3000];

void divCon(int n, int m, int x)
{
	int check = map[n][m];

	for (int i = n; i < n + x; ++i) {
		for (int j = m; j < m + x; ++j) {
			if (check == -1 && map[i][j] != -1) {
				check = 2;
			}
			else if (check == 0 && map[i][j] != 0) {
				check = 2;
			}
			else if (check == 1 && map[i][j] != 1) {
				check = 2;
			}
			if (check == 2) {
				int div = x / 3;
				divCon(n, m, div);
				divCon(n + div, m, div);
				divCon(n + div * 2, m, div);

				divCon(n, m + div, div);
				divCon(n + div, m + div, div);
				divCon(n + div * 2, m + div, div);

				divCon(n, m + div * 2, div);
				divCon(n + div, m + div * 2, div);
				divCon(n + div * 2, m + div * 2, div);
				return;
			}
		}
	}

	if (check == -1) {
		++c[0];
	}
	else if (check == 0) {
		++c[1];
	}
	else if (check == 1) {
		++c[2];
	}

	return;
}

int main(int argc, char *argv[])
{
	int n;

	cin >> n;

	memset(map, 0, sizeof(map));
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> map[i][j];
		}
	}

	divCon(0, 0, n);

	cout << c[0] << endl;
	cout << c[1] << endl;
	cout << c[2] << endl;

	return 0;
}