백준 01992 - 쿼드트리

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

1992번: 쿼드트리

 

고려사항

• 2630 번 문제와 유사
• 압축이 안되어서 4분할을 할 시에는 앞, 뒤에 ( ) 추가
• 2630 번 처럼 n == 1 인 상황 예외 처리 x
  2630 은 비교 대상이 인자로 넘겨 받은 값이라 n이 1이어도 isComplete 아닐 수 있지만,
  위 문제는 비교 대상이 n이 1이라면 그 원소 자체이기 때문에 무조건 isComplete 이다!

 

#include <iostream>
#include <string>
using namespace std;

char video[64][64];

string divide(int y, int x, int n){
    string str;
    bool isComplete = true;

    char target = video[y][x];
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(video[y+i][x+j] != target){
                isComplete = false;
                break;
            }
        }
    }

    if(isComplete){
        str.push_back(target);
        return str;
    }

    str.append("(");
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            str.append(divide((y+i*n/2), (x+j*n/2), n/2));
        }
    }
    str.append(")");
    return str;
}

int main() {
    int n;

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>video[i];
    }

    string ans = divide(0,0,n);
    cout<<ans;
    return 0;
}