백준 1992번 - 쿼드트리(C++/분할 정복/ 재귀 함수)

문제

접근법

저번에 풀었던 1780번 종이의 개수와 거의 똑같은 문제라 봐도 문제 없을듯 하다.

같은 색깔(숫자)가 나올때 까지 4등분으로 분할하고, 같은 색깔이 나오면 그때서야 출력을 하면 된다.

처음 입력이 모든숫자가 1이면 1, 0이면 0을 출력하면 된다.

 

문제를 이해했다면 괄호를 어떻게 출력할지는 고민하지 않았다.

재귀 함수 특성상 함수가 어떻게 돌아갈지 시뮬레이션 돌리기가 힘든 부분이 있는거 같다.

divided했을때 같은수면 그 수를 출력해주고, 다른수면

	cout << "(";
	divided(x, y, size / 2);
	divided(x, y + size / 2, size / 2);
	divided(x + size / 2, y, size / 2);
	divided(x + size / 2, y + size / 2, size / 2);
	cout << ")";

범위를 지정해서 재귀함수 를 돌린다. 

 

 

 

코드

#include <iostream>

using namespace std;

int arr[64][64];

void divided(int x, int y, int size)
{
	int num = arr[x][y];
	bool isSame = true;
	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{
			if (num != arr[i][j])
			{
				isSame = false;
			}
		}
	}
	if (isSame)
	{
		cout << num;
		return;
	}
	cout << "(";
	divided(x, y, size / 2);
	divided(x, y + size / 2, size / 2);
	divided(x + size / 2, y, size / 2);
	divided(x + size / 2, y + size / 2, size / 2);
	cout << ")";
}

int main()
{
	int N;
	cin >> N;

	string num;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		for (int j = 0; j < num.size(); j++)
		{ 
			arr[i][j] = num[j] - '0';
		}
	}
	divided(0, 0, N);
}