(백준/C++) 1780_종이의 개수

1780번: 종이의 개수 문제는 분할 정복(Divide and Conquer) 문제입니다.

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

만약 이전에 1992번: 쿼드트리 (acmicpc.net) 문제나 2630번: 색종이 만들기 (acmicpc.net) 문제를 풀어보셨다면 쉽게 푸실 수 있는 문제입니다.

---

접근법

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

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

1) 분할(Divide)

현재 영역의 데이터가 모두 같은 값인지 확인합니다.

만약 모두 같은 값이 아니라면, $N×N$ 사이즈의 종이를 $\frac{N}{3}×\frac{N}{3}$으로 나눕니다.

2) 정복(Conquer)

만약 나눠진 종이가 모두 같은 숫자(-1, 0, 1)로 채워져 있다면, 해당 숫자의 카운트를 증가시킵니다. 그렇지 않다면, 분할 단계를 반복합니다.

기저 사례(Base Case): 종이의 크기가 $1×1$이 되면, 해당 칸의 숫자(-1, 0, 1)의 카운트를 증가시킵니다

3) 결합(Combine)

정복 단계의 결과를 합쳐 최종 결과를 출력하는 단계입니다.

이 문제에서는 전역 변수로 해당 숫자를 증가 시켰다면, 따로 결합 단계는 존재하지 않습니다. 하지만, 리턴 값과 같은 방식으로 설계했다면, 해당 값들을 결합해야 합니다.

---

풀이

제 풀이에서는 기저 사례를 size를 줄여가며 호출하기 때문에, for문에서 걸러집니다.

#include <iostream>
using namespace std;

int paper[2187][2187];
int numCnt[3];

void solve(int x, int y, int size)
{
	//데이터를 확인한다.
	int check = paper[x][y];
	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{
			if (check != paper[i][j])
			{
				//데이터가 서로 다르면 한 번 더 9칸으로 잘라야 한다.
				int nextSize = size / 3;
				for(int _x = 0; _x < 3; _x++)
				{
					for(int _y = 0; _y < 3; _y++)
					{
						solve(x + _x * nextSize, y + _y * nextSize, nextSize);
					}
				}
				return;
			}
		}
	}

	numCnt[check + 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];
		}
	}

	solve(0, 0, N);

	for(const int& n : numCnt)
		cout << n << '\n';
}