백준_쿼드트리

[ 해결 방법 ]

재귀를 이용해서 문제를 풀었다. 재귀함수(시작점, 종료점)처럼 함수를 만들었다. 시작점부터 종료점까지 for문을 돌면서 색이 모두 같으면 그 색을 출력했고 다르면, 시작점부터 종료점까지의 면적을 4등분해서 4개의 재귀를 호출했다.

[ 코드 ]

#include <iostream>
#define MAX	65
using namespace std;
int N;
bool img[MAX][MAX];
void div(int sx, int sy, int ex, int ey)
{
	bool p_cr, cr;
	int cnt = 0;
	p_cr = cr = img[sy][sx];
	for (int y = sy; y <= ey; y++)
	{
		for (int x = sx; x <= ex; x++)
		{
			cr = img[y][x];
			if (p_cr != cr)
			{
				cout << "(";
				div(sx, sy, (ex + sx) / 2, (ey + sy) / 2);
				div((ex + sx) / 2 + 1, sy, ex, (sy + ey) / 2);
				div(sx, (sy + ey) / 2 + 1, (sx + ex) / 2, ey);
				div((sx + ex) / 2 + 1, (sy + ey) / 2 + 1, ex, ey);
				cout << ")";
				return;
			}
			else 
			{
				cnt++;
				p_cr = cr;
			}	
		}
	}
	if (cnt == ((ex - sx + 1) * (ey - sy + 1)))
		cout << img[sy][sx];
}
int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) 
	{
		char line[MAX];
		cin >> line;
		for (int j = 1; j <= N; j++) 
			img[i][j] = line[j - 1] - '0';
	}
	div(1, 1, N, N);
}