백준 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;
}