BOJ 1992 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

분할 정복으로 풀 수 있는 문제다.

처음엔 문제가 이해되지 않았는데 다음날 다시 읽어보니 이해가 됐다.

한 사각형에서 색이 전부 같지 않으면 ( 를 열고 쪼개 주고 전부 같은 색이면 )를 닫는다.

재귀적으로 들어갈 때에 좌상, 우상, 좌하, 우하 순서로 가는것에 주의해야 한다.

#include <iostream>
#include <string>
using namespace std;	
string ar[65];

void compress(int x, int y, int n) {
	auto tmp = ar[x][y];
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (tmp != ar[i][j]) {
				cout << '(';
				compress(x, y, n / 2);
				compress(x, y + n / 2, n / 2);
				compress(x + n / 2, y, n / 2);
				compress(x + n / 2, y + n / 2, n / 2);
				cout << ')';
				return;
			}
		}
	}
	cout << tmp;
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> ar[i];
	compress(0, 0, n);
	cout << endl;

	return 0;
}

크게 어려운 부분은 없었다.