[백준 2630] 색종이 만들기

● 문제 : 백준 2630번 : 색종이 만들기

2630번: 색종이 만들기

 

● 알고리즘

- 분할정복

 

● 문제 풀이

입력받는 길이가 최대 128이므로 130*130 크기의 이차원 배열과 정답으로 출력할 하얀색 종이의 개수를 나타내는 white, 파란색 종이의 개수를 나타내는 blue를 선언한 후 시작한다.

가장 큰 색종이부터 차근차근 분할해가며 정답을 구한다. 현재 색종이가 모두 0으로 이루어져있다면 white를 1 증가시키고 1로 이루어져있다면 blue를 1 증가시킨다. 만약 모두 0이나 1로 이루어져 있지 않다면 색종이를 4분할하여 또 다시 검사한다. 이 과정을 재귀함수로 구현하면 되는데, 나는 함수의 인자를 (색종이 맨 왼쪽 위의 x좌표, 색종이 맨 왼쪽 위의 y좌표, 색종이 길이) 로 정했다. 분할을 하는 divde 함수와 한 숫자로 이루어져있는지 검사하는 check 함수를 따로 만들어 조금 더 직관적이게 하였다.

check함수를 통해 모두 0으로 이루어져 있다면 white를 1 증가시키고

1로 이루어져 있다면 blue를 1 증가시키고

둘 다 아니라면 아래와 같이 색종이를 4분할하여 진행해간다. 

divide(x, y, n / 2);
divide(x, y + n / 2, n / 2);
divide(x + n / 2, y, n / 2);
divide(x + n / 2, y + n / 2, n / 2);

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

int N;
vector<vector<int>>arr(130, vector<int>(130));
int white = 0, blue = 0;
int check(int x, int y, int n)
{
	int cnt1 = 0, cnt0 = 0;
	for (int i = x; i < x + n; i++)
	{
		for (int j = y; j < y + n; j++)
		{
			if (arr[i][j] == 0)
				cnt0++;
			else
				cnt1++;
		}
	}
	if (cnt0 == 0)
		return 1;
	else if (cnt1 == 0)
		return 0;
	else
		return 2;
}
void divide(int x, int y, int n)
{
	if (check(x, y, n) == 1)
		blue++;
	else if (check(x, y, n) == 0)
		white++;
	else
	{
		divide(x, y, n / 2);
		divide(x, y + n / 2, n / 2);
		divide(x + n / 2, y, n / 2);
		divide(x + n / 2, y + n / 2, n / 2);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	}
	divide(0, 0, N);
	cout << white << "\n" << blue;
	return 0;
}