BOJ 1992 쿼드트리

이 문제는 전형적인 분할 정복과 재귀를 사용하여 풀이하는 문제이다. 분할 할때 '('를 출력하고 정복시 ')'를 출력해주면 된다. 이와 비슷한 문제로 백준 2630 색종이 만들기가 있다.

2630번: 색종이 만들기

위의 색종이 만들기 문제의 풀이는 여기를 참고하면 된다.

 

다음은 이 문제 풀이이다.

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

char map[64][64];
string result = "";

void solution(int x, int y, int num) // num은 분할 크기
{
	char startNum = map[x][y];

	for(int i = 0; i < num; i++)
	{
		for(int j = 0; j < num; j++)
		{
			if(map[x + i][y + j] != startNum)
			{
				result.push_back('(');
				int next = num / 2;
				solution(x, y, next);
				solution(x, y + next, next);
				solution(x + next, y, next);
				solution(x + next, y + next, next);
				result.push_back(')');
				return;
			}
		}
	}
	result.push_back(startNum);
}

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

	memset(map, ' ', sizeof(map));

	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for(int j = 0; j < s.size(); j++)
		{
			map[i][j] = s[j];
		}
	}

	solution(0, 0, n);
	
	cout << result;
}