[백준] 1992 쿼드 트리

백준 1992 쿼드 트리

• https://www.acmicpc.net/problem/1992

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

string video[65];

bool allSameColor(int x, int y, int size, char color) {
	for (int i = x; i < x + size; ++i)
		for (int j = y; j < y + size; ++j)
			if (video[i][j] != color)
				return false;
	return true;
}

string quadTree(int x, int y, int size) {
	if (size == 1) return to_string(video[x][y] - 48);

	if (allSameColor(x, y, size, '0')) return to_string(0);
	if (allSameColor(x, y, size, '1')) return to_string(1);

	int half = size / 2;
	string upperLeft = quadTree(x, y, half);
	string upperRight = quadTree(x, y + half, half);
	string lowerLeft = quadTree(x+ half, y, half);
	string lowerRight = quadTree(x+ half, y+ half, half);

	return "(" + upperLeft + upperRight + lowerLeft + lowerRight + ")";
}

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

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
			cin >> video[i];
		
	cout << quadTree(0, 0, N);
	return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int N;
vector<string> board;

string answer = "";

void quadTree(int r, int c, int size) {
	if (size == 1) {
		answer += board[r][c];
		return;
	}

	bool flag = true;
	for (int i = r; i < r + size; ++i) {
		if (!flag) break;

		for (int j = c; j < c + size; ++j) {
			if (board[r][c] != board[i][j]) {
				flag = false;
				break;
			}
		}
	}

	if (flag) {
		answer += board[r][c];
	}
	else {
		answer += '(';
		int halfSize = size / 2;
		quadTree(r, c, halfSize);
		quadTree(r, c + halfSize, halfSize);
		quadTree(r + halfSize, c, halfSize);
		quadTree(r + halfSize, c+ halfSize, halfSize);
		answer += ')';
	}
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; ++i) {
		string input;
		cin >> input;
		board.push_back(input);
	}

	quadTree(0, 0, N);
	cout << answer;
	return 0;
}