[1992] 쿼드트리

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

1992번: 쿼드트리

<문제>

분할정복, 구역을 정사각형단위로 1/4씩 분할하고, 구역 전체가 동일한 문자로 구성되었을때 해당 문자를 출력,

구역을 1/4씩 분할하기 직전에 '('를, 분할한 후에 ')'를 출력해주면 출력형식을 맞춰줄 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
char a[200][200];
bool isSame(int d, int r, int c) {
    int i, j;
    char x = a[r][c];
    for (i = r; i < r + d; i++) {
        for (j = c; j < c + d; j++) {
            if (i < 0 || j < 0 || i >= n || j >= n) continue;
            if (x != a[i][j]) return false;
        }
    }
    return true;
}
void f(int d, int r, int c) {
    if (isSame(d, r, c) == true) {
        cout << a[r][c];
    } else {
        cout << '(';
        f(d / 2, r, c);
        f(d / 2, r, c + d / 2);
        f(d / 2, r + d / 2, c);
        f(d / 2, r + d / 2, c + d / 2);
        cout << ')';
    }
}
int main(void) {
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) cin >> a[i][j];
    f(n, 0, 0);
    return 0;
}