[백준/C++] 1992번: 쿼드트리

 

풀이

간단한 분할정복 문제이다.

#include <iostream>
#include <string>

using namespace std;

string str[64];

void conquer(int y, int x, int size) {
	char state = str[y][x];

	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			if (state != str[i][j]) {
				cout << '(';
				conquer(y, x, size / 2);
				conquer(y, x + size / 2, size / 2);
				conquer(y + size / 2, x, size / 2);
				conquer(y + size / 2, x + size / 2, size / 2);
				cout << ')';

				return;
			}

	cout << state;
}

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> str[i];

	conquer(0, 0, n);

	return 0;
}