[백준] 분할정복 - 1992. 쿼드트리(문제푸는중)

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

 

출력

영상을 압축한 결과를 출력한다.

 

예제 입력1

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

 

예제 출력1

((110(0101))(0010)1(0001))

 

생각

처음에는 문제이해가 잘 되지 않아서 한참을 들여다봤다. 예시 입력을 직접 풀어보고 이해해야지 문제를 풀 수 있을 거라 생각하는 건지 자꾸 풀려고한다. 예제 문제를 풀어보고 접근해보는 방식도 물론 좋지만, 잘 안된다면 일단 알고리즘적으로 생각해서 해결위주로 방향을 틀어야한다. 예제 문제를 굳이 직접 풀려고 낑낑대다가 보니 시간이 훌쩍 지나간 것을 보고 정신이 번쩍 들었다.  

 

Z문제처럼 좌표로 풀어야겠다고는 감을 잡았었다. 처음에 내가 생각했던 것은 좌표값의 합으로 해서 합이 0이거나 사이즈값과 같다면 0과 1을 출력해주고 작게 쪼개어나가는 것으로 생각했는데 잘 풀리지 않아서 결국 구글링으로 다른 풀이를 찾아보았다. 

그런데, 예제입력을 넣어서 출력은 제대로 나오는데 이상하게 제출하면 틀렸다고 나온다. 

 

작성한 코드

#include <iostream>

using namespace std;
int arr[64][64];

void compress(int x, int y, int n){ //x:x좌표, y:y좌표, n:사이즈
    bool flag = true;
    
    if(n==1){
        cout << arr[x][y];
        return;
    }
    
    int divide = n/2;
    int pixel = arr[x][y];
    for(int i=x; i<x+n && flag ; i++){
        for(int j=y; j<y+n && flag; j++){
            if(pixel!=arr[i][j]){
                flag = false;
            }
        }
    }

    if(flag){ // 모든 수가 같다면 출력한다.
        cout << pixel;
        return;
    }else{ // 같지 않았다면
        cout << '(';
        compress( x, y, divide);  //왼쪽 위
        compress( x, y+divide, divide); //오른쪽 위
        compress( x+divide, y, divide); //왼쪽 아래
        compress( x+divide, y+divide, divide); //오른쪽 아래
        cout << ')';
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%1d", &arr[i][j]);
        }
    }
    
    compress(0, 0, n);
    return 0;
}