[백준] 1992 쿼드 트리

이전에 블로그에 올렸던 문제 색종이 만들기 문제와 매우 유사한 문제지만 출력방식이 다르다.

처음에 문제를 봤을 때 이해가 정말 안됐었다..

 

색종이 만들기 문제는 파란색, 하얀색 종이의 개수를 구하는 문제라면

해당 문제는 1과 0이 정사각형 모양으로 반복되는 구간이 있다면 1로 압축하는 문제이다.

예를들어 

1	1	0	0
1	1	0	0
1	1	1	1
0	0	1	1

이와 같이 주어진 경우 (10(1100)1)로 출력할 수 있다.

4등분을 먼저 하면 아래와 같이 볼 수 있다.

1번	2번
3번	4번

1번의 경우 모두 같은 숫자 1로 구성되어 있으므로 1로 압축을 할 수 있다.

2번의 경우에도 0으로 모두 구성되어 있으므로 0으로 압축할 수 있다.

3번의 경우 1과 0이 섞여 있으므로 다시 한번 재귀를 통해 4등분을 하면

각각의 요소가 따로따로 구분된다.

따라서 1,1,0,0으로 구성할 수 있다.

4번의 경우에는 모두 같은 숫자이므로 1로 압축할 수 있다.

따라서 (10(1100)1) 이러한 출력이 된다.

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input1992(65,vector<int>(65,0));

void recursive1992(int N, int x, int y){

    if(N==1){
        if(input1992[x][y] == 1)
            cout<<"1";
        else if(input1992[x][y] == 0)
            cout<<"0";
        return;
    }
    
    bool oneCheck1992 = false;
    bool zeroCheck1992 = false;
    
    for(int i=x;i<x+N;i++){
        for(int j=y; j<y+N;j++){
            if(input1992[i][j] != 1)
                oneCheck1992 = true;
            if(input1992[i][j] != 0)
                zeroCheck1992 = true;
        }
    }
    
    if(!oneCheck1992){
        cout<<"1";
        return;
    }
    
    if(!zeroCheck1992){
        cout<<"0";
        return;
    }
        
    cout<<"(";
    recursive1992(N/2, x, y);
    recursive1992(N/2, x, y + (N/2));
    recursive1992(N/2, x + (N/2), y);
    recursive1992(N/2, x + (N/2), y + (N/2));
    cout<<")";
}

void tree1992(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin>>N;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            char a;
            cin >> a;
            input1992[i][j] = a - '0';
        }
    }
    
    recursive1992(N, 1, 1);
}