🖊️ 문제

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

---

🖊️ 풀이

일단 쿼드트리
하 진짜 개빡친다 풀긴 쉽게 풀었는데 input을 잘못넣었음 ㅡㅡ!!!

분할정복을 통해서 size를 나눠가며 계속 재귀로 해주면 된다.

만약 맵 전체가 0이라면 압축하면 0.

분할되는 순간 부터 괄호()가 붙기 시작한당.
루프를 돌다가 나눠야 하는 부분이 나타나면 나눠서 압축한다.
압축 들어가면 원래 탐색하던거는 안해도 되니까 해당 함수는 리턴해준다. 어차피 거기서는 0이나 1이 안나옴.

아래 코드에서 result += '(';, result += ')';으로 감싸져 있는 부분이 압축 그 자체이다.

왜냐면 압축된 결과는 무조건 출력을 할거고
압축이 될 때까지 파고들어가야되니까

cout이 오래걸리니까 result string 객체에 결과를 모아서 한 번에 출력했다.

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

string result = "";
char v[65][65];

void Divide(int x, int y, int size)
{
	char first = v[x][y];
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (v[i][j] != first) {
				result += "(";
				Divide(x, y, size / 2);
				Divide(x, y + size / 2, size / 2);
				Divide(x + size / 2, y, size / 2);
				Divide(x + size / 2, y + size / 2, size / 2);
				result += ")";
				return;
			}
		}
	}
	result += first;
}

int main()
{
	int N;
	cin >> N;

	string input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		for (int j = 0; j < N; j++) {
			v[i][j] = input[j];
		}
	}

	Divide(0, 0, N);

	cout << result << endl;
}