[C++] 백준 2630: 색종이 만들기

안녕하세요. 오늘 풀어볼 문제는 백준 색종이 만들기입니다.

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

 

이번 문제는 분할 정복 문제인데요.

분할 정복 알고리즘은 상대적으로 큰 문제를 더 작은 단위로 재귀적으로 호출하면서 해결하는 알고리즘입니다.

 

이 문제는 크게 두 가지 과제로 나눌 수 있습니다.

첫 번째는 범위 안의 색종이가 한 가지 색으로만 되어있는지 판별하는 부분구요.

두 번째는 색종이를 자르고 각 색종이에 대해 문제를 해결하는 부분입니다.

두 번째 과제가 분할 정복 알고리즘이 되겠네요.

 

첫 번째 색종이 색을 판별하는 방법입니다.

크기가 s인 색종이에서 색에 상관없이 칸의 개수는 s*s에요.

그럼 색이 파란 칸(1)의 개수를 세었을 때 개수가 0 또는 s*s라면 해당 색종이는 하나의 색으로만 이뤄져 있는 것입니다.

 

두 번째로 색종이를 자르는 방법입니다.

 

색종이는 색을 판별했을 때 하나의 색으로 이뤄져있지 않을 때 자르면 돼요.

 

하나의 색종이를 자르면 4개로 나누어지는데요,

원래 색종이의 좌측상단의 좌표가 x, y라면

x, y

x, y + s / 2

x + s / 2 , y

x + s / 2 , y + s / 2

의 좌표로 재귀해주면 됩니다.

 

#include <iostream>
using namespace std;

int N;
int paper[130][130];
int cnt[2];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void f(int x, int y, int sz) {
	if (paper[x][y] == 2)
		return;

	int b_cnt = 0;

	for (int i = x; i < x + sz; i++)
		for (int j = y; j < y + sz; j++)
				b_cnt += paper[i][j];

	if (b_cnt == sz * sz || b_cnt == 0)
		cnt[paper[x][y]]++;
	else {
		f(x, y, sz / 2);
		f(x, y + sz / 2, sz / 2);
		f(x + sz / 2, y, sz / 2);
		f(x + sz / 2, y + sz / 2, sz / 2);
	}

}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> paper[i][j];

	f(0, 0, N);

	cout << cnt[0] << '\n' << cnt[1];
}