[C++] 백준 2630번 색종이 만들기

분할 정복 문제입니다.

색종이의 색이 다 같을 때 까지 색종이를 4조각으로 자를 때
흰색 종이와 파란색 종이의 개수를 구해야합니다.

함수에 파라미터를 (x시작 지점, y시작 지점, x끝 지점, y끝 지점) 으로 하였습니다.
그리고 종이안의 색을 비교해서 다른것이 있다면 4조각으로 잘라서 다시 함수를 실행해줍니다.

xs = x의 시작지점
ys = y의 시작지점
xe = x의 끝지점
ye = y의 끝지점

func(xs, ys, (xs+xe)/2, (ys+ye)/2)     // 왼쪽 위
func((xs+xe)/2, ys, xe, (ys+ye)/2)     // 오른쪽 위
func(xs, (ys+ye)/2, (xs+xe)/2, ye)     // 왼쪽 아래
func((xs+xe)/2, (ys+ye)/2, xe, ye)     // 오른쪽 아래

이를 반복해서 실행해주어서 색종이에 한 색이 남으면 카운트해줍니다.

 

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

int countW = 0;
int countB = 0;
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) {
				divCon(ns, ms, (ns + ne) / 2, (ms + me) / 2);
				divCon((ns + ne) / 2, (ms + me) / 2, ne, me);
				divCon(ns, (ms + me) / 2, (ns + ne) / 2, me);
				divCon((ns + ne) / 2, ms, ne, (ms + me) / 2);
				return;
			}
		}
	}

	if (check == 0) {
		++countW;
	}
	else if (check == 1) {
		++countB;
	}

	return;
}

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

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

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

	divCon(0, 0, n, n);

	cout << countW << endl;
	cout << countB << endl;

	return 0;
}