[백준/BOJ] 2630번 색종이 만들기 (C/C++)

 

백준 온라인 저지(BOJ) 2630번 색종이 만들기

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

2630번: 색종이 만들기

* 사용언어 : C언어, C++

 

1. 문제

2^k (k는 1 ~ 7) 크기의 정사각형 map (값은 0 또는 1)

전체에서 4등분 하면서 0 또는 1만 존재하는 정사각형의 개수 출력

 

2. 풀이

분할 정복 기초 문제입니다.

재귀 함수를 만들고 함수 내에서 재 호출하게 구성하면 됩니다.

 

원활한 판단을 위해 map 의 좌상단 값을 fv 라고 저장한 뒤

map 을 순회하면서 각 값이 fv 와 다른지를 확인했습니다.

하나라도 fv 와 다르다면 즉시 반복문을 탈출하도록 작성했습니다.

(그 후 4분할 한 뒤 재귀 함수 4회 호출)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 128;
int map[LM][LM], cnt[2];

void checkMap(int sy, int sx, int n) {
	int fv = map[sy][sx];
	int onlyOne = 1;
	for (int y = sy; y < sy + n; ++y) {
		for (int x = sx; x < sx + n; ++x) {
			if (fv != map[y][x]) {
				onlyOne = 0;
				break;
			}
		}
		if (onlyOne == 0) break;
	}

	if (onlyOne == 1) {
		++cnt[fv];
	}
	else {
		checkMap(sy, sx, n / 2);
		checkMap(sy + n / 2, sx, n / 2);
		checkMap(sy, sx + n / 2, n / 2);
		checkMap(sy + n / 2, sx + n / 2, n / 2);
	}
}

int main(){
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n;
	scanf("%d", &n);
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			scanf("%d ", &map[y][x]);
		}
	}

	checkMap(0, 0, n);
	printf("%d\n%d\n", cnt[0], cnt[1]);
	return 0;
}