대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.
이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.
이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은 xwwwb로 압축됩니다.
그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.
쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 220 × 220 을 넘지 않습니다.
각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int pos;
int i;
string reverse(string& pic)
{
char pos = pic[i++];
if(pos=='b') return "b";
if(pos=='w') return "w";
string topL=reverse(pic);
string topR=reverse(pic);
string botL=reverse(pic);
string botR=reverse(pic);
return "x" + botL + botR + topL + topR;
}
int main()
{
int t;
cin >> t;
while(t--)
{
string pic;
cin >> pic;
cout << reverse(pic) << endl;
i=0;
}
return 0;
}
어떤 식으로 접근해야할지 30분을 접근했다. 재귀함수 안에 두개의 queue
를 이용해 위, 아래를 따로 나누어 생각하려 했지만 굉장히 복잡한 생각이었다. 책에서는 두 가지 방법을 제시하는데
난 압축을 해제하지 않고 queue
를 이용해 해결하려 하였으나 생각보다 복잡하여 책을 참고하였다.
책에서 첫번째 방법이 내 생각과 유사했는데 내 생각보다 더 깔끔하고 구체적이었다.
그리고 두번째 방법인 백트래킹을 이용한 풀이는 코드 자체가 간단했다. 하지만 사고자체는 지금 내 수준에서는 어려운 듯하다.
재귀적으로 생각하는 힘과 구현력을 키워야겠다.