[Silver 1] 1992 쿼드 트리

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

 

원래 존재하는 image의 값이 다를 경우 4등분 해야 함을 알 수 있다.

이는 분할 정복을 사용해 문제를 해결해야 함을 알 수 있다.

 

자를 때는 왼쪽 위, 오른 쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 잘라야한다.

등분은 4등분이기 때문에 area/2를 해준다.

quadTree(y, x, area/2);
quadTree(y, x + area/2, area/2);
quadTree(y + area/2, x, area/2);
quadTree(y + area/2, x + area/2, area/2);

 

배열을 순회하여 같은 문자가 아닐 시에 자르고 같으면 값을 출력해준다.

 

#include <iostream>
using namespace std;

int N;
char image[65][65];

void quadTree(int y, int x, int area){
    bool same = true;

    for(int i = y;i<area + y;i++){
        for(int j = x;j<area + x;j++){
            if(image[i][j] != image[y][x]){
                same = false;
                break;
            }
        }
        if(!same)
            break;
    }
    
    if(!same){
        cout<<"(";
        quadTree(y, x, area/2);
        quadTree(y, x + area/2, area/2);
        quadTree(y + area/2, x, area/2);
        quadTree(y + area/2, x + area/2, area/2);
        cout<<")";
    }
    else{
        if(image[y][x] == '0')
            cout<<0;
        else
            cout<<1;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++)
            cin>>image[i][j];
    }

    quadTree(0, 0, N);
}