[백준] 2630번 - 분할 정복 알고리즘

#include <iostream>

using namespace std;

int n;
int** ar;
int  blue= 0,white = 0;

void ColorPaper(int x, int maxX, int y, int maxY) {
	bool re = false;
	int init = ar[y][x];
	for (int i = y; i < maxY ; i++) {		
		for (int j = x; j < maxX; j++) {
			if (ar[i][j] != init) 
				re = true;							
		}	
	}	
	if (re) {
		int size = maxX - x;
		ColorPaper(x, x + size / 2, y, y + size / 2);
		ColorPaper(x + size / 2, x + size, y, y + size / 2);
		ColorPaper(x, x + size / 2, y + size / 2, y + size);
		ColorPaper(x + size / 2,x + size,y + size / 2,y + size);
	}
	else {
		if (init == 1)
			blue++;
		else
			white++;
	}
}

int main() {	
	cin >> n;	
	ar = new int* [n];
	for (int i = 0; i < n; i++)
		ar[i] = new int[n];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			ar[i][j] = a;
		}
	}	
	
	ColorPaper(0, n, 0, n);	

	cout << white << '\n' << blue;

	for (int i = 0; i < n; i++)
		delete[] ar[i];
	delete[] ar;
}

 

먼저 동적 2차원 배열을 할당해 입력값을 저장하도록 했는데 이중 포인터를 만들고 이중 포인터를 정수 배열을 담고 있는 포인터들의 배열을 가리키도록 지정했다. 

 

동적 2차원 배열 할당

 

그리고 구간의 최소 x, 최대 x, 최소 y, 최대 y를 인수로 받는 함수 ColorPaper을 만들어 구간 내에 색종이들의 색이 모두 같을 때 까지 계속해서 구간을 4개의 사분면으로 나누는 재귀 호출을 진행했다. 그래서 구간 내에 색종이들의 색이 모두 같을 경우 파랑색일 때 blue, 하얀색일 때 white가 증가한다. 이렇게 조건을 만족할 때 까지 계속해서 분할해서 재귀적으로 함수를 실행하는 알고리즘을 분할 정복 알고리즘이라고 한다.