[C++]1992번 : 쿼드트리

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

1992번: 쿼드트리

 

비트값을 압축하는 문제이다. x, y축 길이가 항상 같고, 주변 4칸을 기준으로 압축하기 때문에 범위를 절반씩 줄여 가며 압축한다.

 

#include <bits/stdc++.h>
using namespace std;
int n;
string m[64];

string zip(int a, int b, int scale){
    char c = m[a][b];
    if(scale == 1) return string(1, m[a][b]);
    for(int x = a; x < a+scale; x++){
        for(int y = b; y < b+scale; y++){
            if(m[x][y] != c){
                return "(" + zip(a, b, scale/2) + 
                zip(a, b+scale/2, scale/2) + zip(a+scale/2, b, scale/2)
                + zip(a+scale/2, b+scale/2, scale/2) + ")";
            }
        }
    }
    return string(1, m[a][b]);
}

int main()
{
    cin >> n;
    for(int x = 0; x < n; x++){
        cin >> m[x];
    }
    cout << zip(0, 0, n);
}

시작 좌표와 매트릭스의 너비를 받은 뒤, for문으로 해당 범위 내의 숫자를 탐색하며 모든 숫자가 같다면 처음 숫자를 반환하고, 하나라도 다른 숫자가 있다면 탐색 범위를 x, y축 절반으로 줄여 나가면서 재귀를 수행한다.