백준 2630 색종이 만들기

 

문제 : https://www.acmicpc.net/problem/2630

 

서론

분할정복 문제

 

풀이

표의 내용을 전수검사해서 전부 1이거나 전부 0이 아니면 4분할 한다.

4분할은 재귀를 통해 전부 1이거나 전부 0일때까지 반복한다.

전부 1이거나 전부 0이면 색종이 수를 +1해주고 리턴한다.

 

4분할의 좌표는 왼쪽 상단 지점을 (x1, y1), 오른쪽 하단 지점을 (x2, y2)로 하고 아래와 같이 분할한다.

1: x1, y1, (x1+x2)/2, (y1+y2)/2)
2: (x1+x2)/2+1, y1, x2, (y1+y2)/2)
3: x1, (y1+y2)/2+1, (x1+x2)/2, y2)
4: (x1+x2)/2+1, (y1+y2)/2+1, x2, y2)

 

구현

//c++

#include <iostream>

int map[129][129];
int blue;
int white;

void divide(int x1, int y1, int x2, int y2) {
	int cntBlue = 0;
	int cntWhite = 0;
	for (int i = y1; i <= y2; i++) {
		for (int j = x1; j <= x2; j++) {
			if (map[i][j] == 1) cntBlue++;
			else cntWhite++;
		}
	}

	//std::cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << std::endl;
	//std::cout << cntBlue << " " << cntWhite << std::endl;

	if (cntBlue == 0) { 
		white++; 
	}
	else if (cntWhite == 0) { 
		blue++;
	}
	else {
		divide(x1, y1, (x1+x2)/2, (y1+y2)/2); //1
		divide((x1+x2)/2+1, y1, x2, (y1+y2)/2); //2
		divide(x1, (y1+y2)/2+1, (x1+x2)/2, y2); //3
		divide((x1+x2)/2+1, (y1+y2)/2+1, x2, y2); //4
	}
	return;
}

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

	divide(0, 0, n-1, n-1);
	std::cout << white << std::endl << blue;
}