[백준 / C++] 2630번: 색종이 만들기 (재귀, 분할 정복)

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

2630번: 색종이 만들기

난이도: solved.ac 실버 2

 

알고리즘 분류

재귀, 분할 정복 (Devide and Conquer)

 

구현 방법

색종이의 맨 왼쪽 위 index부터 시작해 색종이의 크기만큼 arr[i][j]를 탐색하다가 맨 왼쪽 위 원소와 다르면 색종이를 4등분 한다.

잘려진 색종이의 한 변의 길이는 현재 색종이 한 변의 길이의 절반이다.

4등분할 때 잘려진 각 색종이의 왼쪽 위 좌표 값을 넘겨주었다. (행: sti, 열: stj)

(4등분 된) 색종이의 모든 숫자가 같으면 해당 숫자로 white인지 blue인지 파악해준다.

 

코드

#include <bits/stdc++.h>

int arr[128][128];
int white, blue;
void paper(int N, int sti, int stj);

int main() {
	int N, i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			scanf("%d", &arr[i][j]);

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

void paper(int N, int sti, int stj) {
	for (int i = sti; i < sti + N; i++) {
		for (int j = stj; j < stj + N; j++) {
			if (arr[i][j] != arr[sti][stj]) {
				paper(N / 2, sti, stj);
				paper(N / 2, sti + N / 2, stj);
				paper(N / 2, sti, stj + N / 2);
				paper(N / 2, sti + N / 2, stj + N / 2);
				return;
			}
		}
	}
	if (arr[sti][stj])
		blue++;
	else
		white++;
}