[백준] 1992 쿼드트리 (C++)

링크: https://www.acmicpc.net/problem/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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

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

---

풀이

N이 언제나 2의 제곱수로 주어지는 것을 알고 분할 정복을 진행하면 풀 수 있는 문제이다.

분할 정복이 낯설거나 익숙하지 않은 경우 어떻게 풀어나가야 할지 막막할 수 있지만,

가로 세로로 각각 2등분을 하여 총 4개의 조각으로 분할하여 정복해나가면 풀어나갈 수 있다.

 

string solve(int y, int x, int size){
    if (size >= 2){
        string a = solve(y, x, size/2);
        string b = solve(y, x+size/2, size/2);
        string c = solve(y+size/2, x, size/2);
        string d = solve(y+size/2, x+size/2, size/2);
        if (a.size() == 1 && a == b && b == c && c == d){
            return a;
        }
        else{
            return '('+a+b+c+d+')';
        }
    }
    else{
        return (video[y][x]);
    }
}

 

size(한 변의 길이)가 2 이상인 경우에는 이를 a, b, c, d 네 조각으로 쪼개어 재귀적으로 값을 구한다.

이후 (abcd)를 리턴해주면 되는데 여기서 조심할 점이 있다.

만약 if (a == b && b == c && c == d) 와 같이 네 덩어리가 모두 같다고 할 경우 다음 반례의 경우 오답이 나온다.

 

0000
1111
0000
1111

output: (0011)

 

여기서 a, b, c, d가 모두 0011로 같으므로 return a가 실행되어 (0011)로 출력될 것이다.

하지만, 옳은 정답은 ((0011)(0011)(0011)(0011))이다.

 

따라서 반드시 네 덩어리가 같은 것을 조사할 때 덩어리의 길이가 1인지도 조사해야 한다.

 

코드

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

string video[64][64];
string solve(int y, int x, int size){
    if (size >= 2){
        string a = solve(y, x, size/2);
        string b = solve(y, x+size/2, size/2);
        string c = solve(y+size/2, x, size/2);
        string d = solve(y+size/2, x+size/2, size/2);
        if (a.size() == 1 && a == b && b == c && c == d){
            return a;
        }
        else{
            return '('+a+b+c+d+')';
        }
    }
    else{
        return (video[y][x]);
    }
}

int main(){
    int n;
    cin >> n;

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

    string answer =  solve(0, 0, n);
    cout << answer;

}