[BOJ] 1992 : 쿼드트리 - travelbeeee

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

---

[ 알고리즘풀이 ]

재귀적으로 함수를 구현해 문제를 분할 정복할 수 있습니다.

먼저, 전체 크기 N x N 배열을 Check 합니다. 이때, N x N 배열이 모두 같다면 값을 출력해주고, 아니라면 4등분을 해서 체크해봐야 합니다. 4등분이 되는 순간 괄호가 생겨야 되므로 '(' 를 출력하고 (N / 2) x (N / 2) 배열에 대해서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 다시 함수를 재귀적으로 호출해서 Check 합니다. 재귀함수가 끝난 후 ')' 를 출력한다면 문제를 해결할 수 있습니다.

#include<iostream>

using namespace std;

int N; 
char map[64][65] = {};

void compression(int r, int c, int s) {
	char temp = map[r][c];
	bool check = false;
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			if (map[r + i][c + j] != temp) {
				check = true;
				i = s, j = s;
			}
	if (!check)
		cout << temp;
	else {
		int k = s / 2;
		cout << '(';
		compression(r, c, k);
		compression(r, c + k, k);
		compression(r + k, c, k);
		compression(r + k, c + k, k);
		cout << ')';
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];
	compression(0, 0, N);
}

---