(백준/C++) 2630_색종이 만들기

2630번: 색종이 만들기 (acmicpc.net) 문제는 분할 정복(Divide and Conquer) 문제입니다.

분할 정복은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 합쳐 원래 문제의 해결책을 찾는 방법입니다.

문제의 예시 그림에서 볼 수 있듯이 가로 세로 절반씩 분할 후 모든 색이 칠해져 있는지 확인하고 그 색이 하얀색인지 파란색인지 묻는 문제입니다.

출처: 백준 - 2630번: 색종이 만들기 (acmicpc.net)

---

접근법

분할 정복(Divide and Conquer)은 세 가지 접근법으로 먼저 생각해볼 수 있습니다.

바로, 분할 - 정복 - 결합 입니다.

1) 분할(Divide)

현재 종이가 모두 같은 색으로 칠해져 있는지 확인합니다.

만약 모두 같은 색이 아니라면, 종이를 가로 세로 절반으로 4개의 동일한 크기의 종이로 나누어 갑니다.

2) 정복(Conquer)

각 부분 문제에 대해 같은 방법으로 재귀적으로 문제를 해결합니다.

즉, 각 부분이 모두 같은 색으로 칠해져 있는지 확인하고, 그렇지 않다면 다시 4개의 부분으로 나눕니다.

기저 사례(Base Case): 만약 종이가 하나의 정사각형 칸으로 구성되어 있거나 모두 같은 색으로 칠해져 있다면, 해당 색의 종이 개수를 1 증가시키고 재귀를 종료합니다.

3) 결합(Combine)

각 부분 문제의 해결책을 합쳐 전체 문제의 해결책을 얻는 단계입니다.

이 문제에서는 각 부분 문제에서 나누어진 종이의 색을 합치는 단계입니다.

---

풀이

이 문제는 전역 변수를 사용하면 결합 단계를 간단하게 만들 수 있습니다.

현재 종이의 모든 칸을 확인하면서 다른 색이 존재하면 4개의 부분으로 나눕니다.

만약, 모든 확인이 끝난다면 모두 같은 색이라는 의미이므로 현재 확인한 색상을 추가해주면 됩니다.

#include <iostream>
using namespace std;

bool paper[128][128];
int blueTotal;
int whiteTotal;
struct coord
{
	int x;
	int y;

	coord operator+(const coord& B) const
	{
		return { B.x + x, B.y + y };
	}
	coord operator-(const coord& B) const
	{
		return { B.x - x, B.y - y };
	}
	coord operator/(const int& n) const
	{
		return { x / n, y / n };
	}
};

void dividePaper(coord start, coord end)
{
	//색종이가 한 칸이라면 종료
	if((end - start).x == 1 || (end - start).y == 1)
	{
		if (paper[start.x][start.y]) blueTotal += 1;
		else whiteTotal += 1;

		return;
	}

	bool check = paper[start.x][start.y];
	for(int i = start.x; i < end.x; i++)
	{
		for(int j = start.y; j < end.y; j++)
		{
			if(check != paper[i][j])
			{
				coord mid = (start + end) / 2;
				dividePaper(start, mid);
				dividePaper({ mid.x, start.y }, { end.x, mid.y });
				dividePaper({ start.x, mid.y }, { mid.x, end.y });
				dividePaper(mid, end);

				return; //다른 색이 나타나면 반복 종료
			}
		}
	}

	//모두 같은 색이라면 확인한 색상을 추가한다.
	if (check) blueTotal += 1;
	else whiteTotal += 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

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

	dividePaper({ 0, 0 }, { N, N });

	cout << whiteTotal << '\n' << blueTotal;
}