[백준 2630] 색종이 만들기

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

2630번: 색종이 만들기

#include <stdio.h>
int n;
int paper[128 + 10][128 + 10];
int w_cnt, b_cnt;

void input(void)
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &paper[i][j]);
		}
	}
}

void cut_paper(int x, int y, int n)
{
	int tmp = 0;
	for (int i = x; i < (x + n); i++) {
		for (int j = y; j < (y + n); j++) {
			if (paper[i][j] == 0) tmp++;	//하얀색으로 칠해진 칸만 세어준다
		}
	}

	if (tmp == n * n) w_cnt++;	//하얀색으로 칠해진 칸이 n * n개 있으면 w_cnt++;
	else if (tmp == 0) b_cnt++;		//하나도 없으면 파란색으로 칠해진 것이므로 b_cnt++;
	else {				//위의 두 경우가 아니라면 해당 영역이 같은 색으로 칠해진 것이 아니므로 
		cut_paper(x, y, n / 2);			//범위 줄여서 재귀함수 호출
		cut_paper(x + n / 2, y, n / 2);	//시작 좌표 옮겨서 재귀함수 호출
		cut_paper(x, y + n / 2, n / 2);
		cut_paper(x + n / 2, y + n / 2, n / 2);
	}
	return;
}

int main(void)
{
	input();
	cut_paper(0, 0, n);		//한변의 길이가 n인 종이를 (0, 0)부터 탐색하겠다.  
	printf("%d\n%d", w_cnt, b_cnt);
	return 0;
}

재린이(재귀함수 + 어린이....)로서 이 문제는 어렵다.

 

//main 함수

가장 고민했었던 점은 재귀 함수를 어디서 어떻게 호출할 것이냐 이다. 

main에서 처음으로 cut_paper라는 재귀함수를 호출할 때는 시작점(0, 0)과 종이의 한 변의 길이를 파라미터로 사용했다. 

앞으로 이 파라미터들을 바꾸면서 종이를 탐색할 것이다. 

 

 

//cut_paper 함수

각 영역을 탐색하기 위해 루프를 돌린다. 

그 전에 tmp 변수를 두고, 만약 paper[i][j]가 0이면, 즉 흰색으로 칠해진 칸이면, tmp++;를 해준다. 

루프를 다 돌고 나서 만약 세어진 tmp의 개수가 n * n과 같다면, 즉 탐색한 영역의 넓이와 같다면, 해당 영역은 모두 흰색으로 칠해져 있다고 볼 수 있다. 따라서 w_cnt++;를 해준다. 

반면에 tmp의 개수가 0이라면, 즉 아무것도 세어지지 않았다면 해당 영역은 모두 파란색으로 칠해져 있다고 볼 수 있다. 따라서 b_cnt++;를 해준다. 

 

마지막으로 위의 두 경우가 아니라면, 즉 탐색 영역이 모두 흰색으로 칠해지거나 파란색으로 칠해진 경우가 아니라면, 시작점을 옮기거나 탐색 영역을 줄여서 다시 탐색을 해야한다. 

이를 위해 cut_paper함수를 재귀적으로 호출하되, 시작점을 옮기거나 탐색 영역을 반으로 줄인 것을 파라미터로 사용한다.