쿼드트리 C++ - 백준 1992

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

분할 정복 문제.

색종이 만들기와 유사한 문제이다.

문제 접근

출력 패턴을 보면 압축한 영상의 크기가 작아질때마다 괄호가 열리고,

닫히는 것을 볼 수 있다.

따라서 영상을 네 개로 분할할 때마다 괄호를 열고,

분할이 끝나면 괄호를 닫아주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string s;
int n;
bool f[64][64];

void solve(int x, int y, int c){
    bool cur=f[x][y];
    bool b=false;
    if(c==1){cout << cur;return;}
    for(int i=0;i<c;i++){
        for(int j=0;j<c;j++){
            if(f[x+i][y+j]!=cur){b=true;break;}
        }
        if(b) break;
    }
    if(!b){cout << cur;return;}
    cout << '(';
    solve(x,y,c/2);
    solve(x,y+c/2,c/2);
    solve(x+c/2,y,c/2);
    solve(x+c/2,y+c/2,c/2);
    cout << ')';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n; for(int i=0;i<n;i++){
        cin >> s;
        for(int j=0;j<n;j++) f[i][j]=s[j]-'0';
    }
    solve(0,0,n);
    return 0;
}