<문제링크>
https://algospot.com/judge/problem/read/QUADTREE
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.
- 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이
b가 됩니다. - 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이
w가 됩니다. - 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는
x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은xwwwb로 압축됩니다.
그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.
쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.
위의 문제에서의 쿼드트리는 재귀적으로 그림을 문자열로 압축해서 표현한다. 그러므로 우리는 위문제의 해결을 위해 재귀를 때놓고 생각할 수 없다고 볼 수 있다. 위문제의 해결반안의 키포인트는 x를 마주쳤을 경우이다. 압축방식을 고려했을때 압축된 문자열의 분석은 다음과 같다. x를 만나면 다음 4개의 문자중에 x가 포함되어 있지 않을시 우리는 이 4개의 문자의 순서를 바꾸기만하면 상하로 뒤집은 그림을 압축한 문자열을 얻을 수 있지만 문제는 4개의 문자중에 x가 포함되어있을 경우이다. x가포함된다면 x뒤에오는 4개를 포함한 5개의 문자가 가장 최근에 발견된 x의 4가지 부분중 한부분을 나타내게되는것인데 이같은 구조는 재귀호출을 사용하면 쉽게 구현이 가능해진다. 코드는 아래와 같다.
string quadTree;
//now는 x의 위치이다. x는 곧 그림의 한부분을 의미하고
//해당하는 부분을 상하로 뒤집은 코드를 반환한다.
string reverseQuad(int now){
//4가지 부분에 대한 암호를 저장
string s[4];
int start = now + 1;
int size = quadTree.size();
for(int i = 0 ; i < 4; ++i)
for(int j = start; j < size; ++j){
if(quadTree[j] != x){
s[i] = quadTree[j];
++start;
break;
}
else{
string temp = reverseQuad(start);
start += temp + 1;
s[i] = "x" + temp;
break;
}
}
}
return s[2] + s[3] + s[0] + s[1];
}
//정답 출력. 위 함수에서는 첫번째 x를 출력하지 않는다.
//쿼드트리의 길이가 1이면 쿼드크리자체가 정답이 된다.
cout << "x" + reverseQuad(0) << endl;
위의 코드를 보면 그림의 한부분이 한개의 문자가 아니라 x를 포함한 쿼드트리의 부분문자열이되면 다음 부분을 결정하기 위해 참조할 인덱스를 start에 저장한다. start를 유기하기 위해 코드가 지저분하고 길어 졌다. 이를 해결하기 위해 우리는 함수의 지역변수를 유지하기 보다는 전역변수나 참조자를 통해 이터레이터나 인덱스 번호를 주고 받는다면 코드를 더 간결하게 만들 수 있을 것이다. 그리고 이러한 방법이 논리오류의 가능성도 줄일 수 있다.
string::iterator it;
string reverseQuad(string::iterator &it){
char haed = *it;
string s[4];
++it;
if(head != 'x')
return head;
else{
s[0] = reverseQuad(it);
s[1] = reverseQuad(it);
s[2] = reverseQuad(it);
s[3] = reverseQuad(it);
}
return "x" + s[2] + s[3] + s[0] + s[1];
}