<C++/백준 1992> 쿼드트리

#include <bits/stdc++.h>

using namespace std;

int n;  // 이미지의 크기 n * n
string s;
char a[101][101];

// 쿼드트리 <압축 함수>
// y, x: 현재 검사할 영역의 시작 좌표
// size: 현재 검사할 영역의 크기 (한 변의 길이)
string quard(int y, int x, int size) {
    // 기저 조건: 더 이상 나눌 수 없는 1x1 크기인 경우
    // 해당 위치' 의 문자를 문자열로 변환하여 반환
    if(size == 1) return string(1, a[y][x]);
    
    // 첫 번째 문자를 기준값으로 저장
    char b = a[y][x];
    string ret = "";   // 결과 문자열 초기화
    
    // 현재 영역의 모든 칸을 검사
    for(int i = y; i < y + size; i++) { // 현재 시작 위치로부터 size 만큼이 범위가 됨
        for(int j = x; j < x + size; j++) {
            // 기준값과 다른 문자가 발견되면 4등분하여 재귀 호출
            if(b != a[i][j]) {
                ret += '(';     // 분할 시작을 나타내는 괄호
                // 4개의 부분으로 분할하여 재귀적으로 압축
                ret += quard(y, x, size / 2);   // 왼쪽 위
                ret += quard(y, x + size / 2, size / 2);    // 오른쪽 위
                ret += quard(y + size / 2, x, size / 2);   // 왼쪽 아래
                ret += quard(y + size /2, x + size / 2, size / 2);   // 오른쪽 아래
                ret += ')';     // 분할 종료를 나타내는 괄호
                return ret;
            }
        }
    }
    
    // 모든 칸이 동일한 값인 경우 그 값을 문자열로 반환
    return string(1, a[y][x]);
    
}

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

    // 이미지 크기 입력
    cin >> n;
    
    // 이미지 데이터 입력
    for(int i = 0; i < n; i++){
        cin >> s;  // 한 줄씩 문자열로 입력받음
        for(int j = 0; j < n; j++){
            a[i][j] = s[j];  // 2차원 배열에 한 문자씩 저장
        }
    }
    
    // 전체 이미지에 대해 쿼드트리 압축 수행 및 결과 출력
    // (0,0)에서 시작하여 크기 n인 영역을 압축
    cout << quard(0, 0, n) << '\n';

    return 0;
}