[C++] 백준 1992번 쿼드트리

분할정복 문제입니다.

사각형이 전부 흰색이면 0, 전부 검정색이면 1을 출력합니다.
사각형 안의 색이 여러개라면
왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로
4방면으로 분할해서 위의 과정을 반복합니다.
분할 할 때 '('를 출력해주고, 분할이 끝났을때 ')'을 출력해줍니다.

 

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

int map[130][130];

void divCon(int ns, int ms, int ne, int me)
{
	int check = map[ns][ms];

	for (int i = ns; i < ne; ++i) {
		for (int j = ms; j < me; ++j) {
			if (check == 0 && map[i][j] == 1) {
				check = 2;
			}
			else if (check == 1 && map[i][j] == 0) {
				check = 2;
			}
			if (check == 2) {
				cout << "(";
				divCon(ns, ms, (ns + ne) / 2, (ms + me) / 2);
				divCon(ns, (ms + me) / 2, (ns + ne) / 2, me);
				divCon((ns + ne) / 2, ms, ne, (ms + me) / 2);
				divCon((ns + ne) / 2, (ms + me) / 2, ne, me);
				cout << ")";
				return;
			}
		}
	}

	cout << check;

	return;
}

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

	cin >> n;

	memset(map, 0, sizeof(map));

	for (int i = 0; i < n; ++i) {
		cin >> s;
		for (int j = 0; j < n; ++j) {
			map[i][j] = s[j] - '0';
		}
	}

	divCon(0, 0, n, n);

	return 0;
}