[1992] 쿼드 트리

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

이 문제는 재귀로 쉽게 해결할 수 있습니다.

문제 해결 순서는

1. 해당 범위의 값이 같은지 확인한다.

2. 1에서 같으면 그 값을 출력한다.

3. 1에서 다르면 '('를 출력하고 재귀를 통해 해당 영역을 4개로 나눈다.

4. 재귀로 들어가서 1 ~ 3까지 순서를 반복한다.

5. 재귀호출이 끝나고 ')'를 출력한다.

풀 코드입니다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[1 << 6][1 << 6 + 1];
 
bool isSame(int x1, int y1, int x2, int y2) {
    char tmp = map[x1][y1];
 
    for (int i = x1; i <= x2; i++) {
        for (int j = y1; j <= y2; j++) {
            if (tmp != map[i][j]) return 0;
        }
    }
 
    return 1;
}
 
void f(int x1, int y1, int x2, int y2) {
 
    if (isSame(x1, y1, x2, y2)) cout << map[x1][y1];
    else {
        cout << '(';
        int midX = (x1 + x2) / 2;
        int midY = (y1 + y2) / 2;
 
        f(x1, y1, midX, midY);
        f(x1, midY + 1, midX, y2);
        f(midX + 1, y1, x2, midY);
        f(midX + 1, midY + 1, x2, y2);
        cout << ')';
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) cin >> map[i];
    
    f(0, 0, n - 1, n - 1);
    
    return 0;
}