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

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

비슷한 문제: (1992)쿼드트리
Link: https://www.acmicpc.net/problem/1992

• 사전에 쿼드트리 문제를 통해 학습된 내용이며, 오히려 조건이 적은 문제였으므로 빠르게 문제 해결
• 재귀에 익숙치 않은 분들에게 가볍게 추천하는 문제

1. 더 이상 자를 수 없을 때까지 반복한다 -> 재귀
2. 똑같은 크기의 네 개의 색종이로 자른다 -> 분할 정복

#include<iostream>
using namespace std;
#define MAX 128
int a[MAX][MAX];
int n, white = 0, blue = 0;

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}
}

bool div(int x, int y, int size) {
	int color = a[x][y];	//0:white, 1:blue
	for (int i = x; i < x + size; ++i) {
		for (int j = y; j < y + size; ++j) {
			if (a[i][j] != color) return true;
		}
	}
	if (color == 0) ++white;
	else ++blue;
	return false;
}

void dfs(int x, int y, int size) {
	if (size == 0) return;
	if (!div(x, y, size)) return;
	dfs(x, y, size >> 1);
	dfs(x, y + size / 2, size >> 1);
	dfs(x + size / 2, y, size >> 1);
	dfs(x + size / 2, y + size / 2, size >> 1);
}

void solution() {
	input();
	dfs(0, 0, n);
	cout << white << '\n' << blue;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

• dfs함수 내에 어디는 size / 2, 어디는 size >> 1로 표현되어 있는데, 시간은 미세하게 size >> 1이 빨라 보통은 비트 연산자를 씁니다.
  다만 비트 연산자가 사칙연산보다 후순위로 동작하는 이유로 계산상의 오류가 생기는 실수를 미연에 방지하기 위해 추가 연산이 있는 경우 / 연산을 사용하는 편입니다.