[백준] 2630번: 색종이 만들기 (재귀)

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

<코드>

#pragma warning (disable: 4996)
#include <stdio.h>

int blue = 0;
int white = 0;
int N = 0;

void func(int col, int row, int *arr, int size) {
	int i, j;
	int color = arr[col * N + row];

	if (size == 1) {
		if (color == 1) blue++;
		else white++;
		return;
	}

	for (i = col; i < col + size; i++) {
		for (j = row; j < row + size; j++) {
			if (color != arr[i * N + j]) {
				func(col, row, arr, size / 2);
				func(col + size/2, row, arr, size / 2);
				func(col, row + size / 2, arr, size / 2);
				func(col + size / 2, row + size / 2, arr, size / 2);
				return;
			}
		}
	}

	if (color == 1) blue++;
	else white++;
	return;
}

int main() {
	int paper[128*128];
	int i, j;

	scanf("%d", &N);
	
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &paper[i * N + j]);
		}
	}

	func(0, 0, paper, N);

	printf("%d\n", white);
	printf("%d", blue);
	return 0;
}

 

<설명>

전체 종이를 일차원 배열에 저장했으며 func함수를 통하여 하얀색과 파란색을 구분하게 했다. 

 

func함수에서는 우선 처음 확인하는 정사각형 종이의 색을 color에 저장하여 모두 같은 색인지 아닌지 확인하는 용을 사용한다.

 

영역의 크기가 1일경우, 더 작게 자를 수 없기 때문에 종이의 색을 확인하여 파란색은 blue를, 하얀색은 white를 increment시킨다. 

 

영역안의 정사각형 종이들을 비교하는데, 같지 않으면영역을 4개로 잘라서 다시 확인한다. 이때 재귀를 사용한다. 

 

만일 영역안의 정사각형 종이들이 모두 같다면 영역의 색을 확인하여 파란색은 blue를, 하얀색은 white를 increment시킨다.