백준 1780 번 - 종이의 개수(C++/분할 정복/재귀함수)

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

접근법

먼저 모두 같은 수인가 체크를하고 (아래 isSameNum함수)

만약 같은 수가 아니라면 2번조건을 충족하지 못하므로, size를 /3 해서 조각내서 탐색해보아야 한다.

나누기 3은 해당 범위의 모든 수가 같을때 까지 반복한다.

 

분할 정복 문제이지만, 재귀 함수를 구현해서 풀면 쉽다.

만약 사이즈가 27이면 27->9->3->1 까지 분해해서 봐야할 수도 있으므로, 탐색범위를 지정해주어서 재귀를 돌면 풀 수 있다.

 

아래 코드에서

void sliced(int start_x, int start_y, int range)
{

	if (!isSameNum(start_x, start_y, range))
	{
		int num = range / 3;
		for (int i = start_x; i < start_x+range; i+=(num))
		{
			for (int j = start_y; j < start_y+range; j+=(num))
			{
				sliced(i, j, num);
			}
		}
	}
}

이 부분이 재귀로 호출해주는 부분이다. 만약 isSameNum을 통과하지 못하면(모두 같은수가 아니라면) 탐색범위를 num으로(현재 범위의 /3) 줄여준다. 그럼 총 (i, i+num, i+num*2), (j, j+num, j+num*2) 부분을 탐색할 것인데, 여기서 다른것들은 같을때까지 쪼개서 탐색한다.

코드는 아래와 같다

 

- 여기서 vector push_back을 쓰다가 시간초과가 났다. 초기 동적배열의 크기를 지정해주고 사용하면 문제는 없을거같지만, 빈 동적배열에 push_back을 계속해주면, size 재할당 및 이동 시간이 걸려서 시간에 불리하므로, 범위를 확실히 아는 알고리즘 문제에서는 배열을 사용하는게 마음 편하다

코드

#include <iostream>
#include <vector>
using namespace std;
int paper[2200][2200];
int cntList[3] = { 0, };

bool isSameNum(int start_x,int start_y, int size)
{
	int compare = paper[start_x][start_y];
	for (int i = start_x; i < start_x+size; i++)
	{
		for (int j = start_y; j < start_y+size; j++)
		{
			if (compare != paper[i][j])
				return false;
		}
	}
	cntList[compare + 1]++;
	return true;
}
void sliced(int start_x, int start_y, int range)
{

	if (!isSameNum(start_x, start_y, range))
	{
		int num = range / 3;
		for (int i = start_x; i < start_x+range; i+=(num))
		{
			for (int j = start_y; j < start_y+range; j+=(num))
			{
				sliced(i, j, num);
			}
		}
	}
}
int main()
{
	int N;
	cin >> N;
	

	int num = 0;

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

	for (int i = 0; i < 3; i++)
	{
		cout << cntList[i] << "\n";
	}
}