백준 1992 - 쿼드트리 (분할정복) C++

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

1992번: 쿼드트리

언제 괄호를 출력해야 하는지 확실히 구분해야 한다.

분할정복이 이뤄지는 시점 시작과 끝에만 괄호를 집어 넣을 것.

그 부분 에만 괄호가 들어가야 하고, 그 이외의 시점에는 숫자만 출력하는 것을 확실히 해야 한다.

 

#include <iostream>
#include <string>
using namespace std;
string answer="";
int quad[64][64];
int num;
 
void printquad(int sx, int ex, int sy, int ey){
    bool same = true;
    int sn = quad[sy][sx];
    int dx = ex-sx;
    int dy = ey-sy;
 
    if(dx==1 && dy==1) {
        cout << sn;
        return;
    }
    for(int i=sy; i<ey; i++) {
        for (int j = sx; j < ex ; j++) {
//            cout<<sn<<"quad ij is"<<quad[i][j]<<"\n";
            if (sn != quad[i][j]) {
//                cout<<"false detected!\n";
                same = false;
            }
        }
    }
    if(same){
        cout<<sn;
    }
    else {
        cout<<"(";
        printquad(sx, sx + dx / 2, sy, sy + dy / 2);
        printquad(sx + dx / 2, ex, sy, sy + dy / 2);
        printquad(sx, sx + dx / 2, sy + dy / 2, ey);
        printquad(sx + dx / 2, ex, sy + dy / 2, ey);
        cout<<")";
    }
    return;
}
 
 
 
 
 
int main(void){
 
    cin>>num;
    for(int i=0; i<num; i++){
        string s;
        cin>>s;
        for(int j=0; j<num;j++){
            quad[i][j]=s[j]-'0';
//            cout<<i<<" "<<j<<" : "<<quad[i][j]<<"  ";
        }
    }
    printquad(0,num,0,num);
}