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

백준 단계별로 풀어보기 [분할 정복] 색종이 만들기

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

2630번: 색종이 만들기

 

[풀이]

재귀호출을 위한 인자로 y의 시작 좌표, x의 시작 좌표, size(width==height)를 전달해준다. 처음 arr[y][x]와 비교하여 다른 색이 붙어있다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나누어 재귀호출을 해준다. 모두 하얀색이었다면 white_color 수를 증가해주고, 모두 파란색이었다면 blue_color 수를 증가해준다. 

 

[코드]

#include <iostream>
#include <string>
#include <algorithm>

int arr[129][129];
int white_color = 0, blue_color = 0;

void cut(int y, int x, int size) {
	int check = arr[y][x];
	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (check == 0 && arr[i][j] == 1) {
				check = 2;
			}
			else if (check == 1 && arr[i][j] == 0) {
				check = 2;
			}

			if (check == 2) {
				cut(y, x, size / 2); // 왼쪽 위
				cut(y + size / 2, x, size / 2); //왼쪽 아래
				cut(y, x + size / 2, size / 2); // 오른쪽 위
				cut(y + size / 2, x + size / 2, size / 2); //오른쪽 아래
				return;
			}
		}
	}
	if (check == 0)
		white_color++;
	else if (check == 1)
		blue_color++;
}

int main() {
	//같은 색으로 칠해져 있지 않으면 n/2 * n/2 로 종이를 자름. 같은 색으로 칠해져 있을 때까지 or n=1 일 때까지.
	//잘라진 하얀색 종이(0)와 파란색 종이(1)의 개수를 구하자.
	int n; //한변의 길이
	std::cin >> n;

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

	cut(0, 0, n);

	std::cout << white_color << "\n" << blue_color;

}