백준 1992 : 쿼드트리

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

1. 접근

• 종이의 개수와 비슷한 방식의 문제. 큰 범위를 보고, 조건에 해당하지 않으면 4개로 분할한다.
  (cf. 종이의 개수에서는 조건에 해당하지 않으면 9개로 분할했다.)
• 분할할 때 괄호를 추가하고, 분할이 끝나면 괄호를 닫는다.
• 각 칸에 들어오는 입력값은 띄어쓰기 없이 주어진다. => 문자열을 사용해서 각 값을 분리한다. (정수로 받은 후 10으로 나누는 방식을 사용했으나, int 타입으로는 64자리까지 나타낼 수 없었다..)

2. 나의 풀이

#include <iostream>
using namespace std;

int map[70][70];
int n;

bool check(int x, int y, int size) {
	if (size == 1) return true;
	int start = map[x][y];
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (start != map[i][j]) return false;
		}
	}
	return true;
}

void divide(int x, int y, int size) {
	if (check(x, y, size)) {
		cout << map[x][y];
	}
	else {
		int nextsize = size / 2;
		cout << "(";
		for (int i = x; i <= x+ nextsize; i+= nextsize) {
			for (int j = y; j <= y+ nextsize; j+= nextsize) {
				divide(i, j, nextsize);
			}
		}
		cout << ")";
	}
	return;
}

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

	cin >> n;
	char tem[70];

	for (int i = 0; i < n; i++) {
		cin >> tem;
		for (int j = n - 1; j >= 0; j--) {
			map[i][j] = tem[j]-'0';
		}
	}

	divide(0, 0, n);
	cout << "\n";

	return 0;
}