쿼드 트리 뒤집기(QUADTREE 난이도:하)

쿼드 트리(QUADTREE)

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있다.

주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 위해 쿼드 트리라는 이름이 붙었다.

 

가장 유명한 예시로 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현한 사례가 있다.

 

쿼드 트리는 2**n * 2**n크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축한다.

 

• 이 그림의 모든 픽셀이 검은 색일 경우 이그림의 쿼드 트리 압축 결과는 그림의 킉에 관계없이 b가 된다.
• 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계 없이 w가 된다.
• 모든 픽셀이 강튼 색이 아니라면, 쿼드 트리는 이그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축한다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다. 예를 들면 그림의 왼쪽 위 4분면은 xwwwb로 압축된다.

 

 

 

압축 풀고 다시 압축하기

처음에 이 문제를 봤을 때, 풀이법이 2가지라고 생각하긴 했다.

1. 압축된 사진을 압축 풀어서 사진을 뒤집고 압축한다.
2. 압축을 다 안풀고 뒤집는다.

 

당연히 후자의 방법이 우아한 정답이라고 생각했지만, 먼저 1번 방법도 고려해봤다.

그러나 1번의 풀이법이 오히려 그닥 간단하지 않은 방법임을 구현하다보면 느낄 수 있었다.

 

 

1. 압축을 푸는 방법

쿼드트리가 재귀적으로 정의되어있기에 쿼드트리를 압축/해제하는 과정은 재귀호출로 구현하는 것이 자연스럽다.

따라서 기저사례를 'b','w'인 경우로, 이때는 배열 전체에 해당색을 칠하고 종료시키면 된다. 그런데 첫글자가 x인 경우에는 decompress()함수로 나머지 부분을 네개로 나누어 재귀호출하면 된다.

 

그러나 여기서 문제는 압축 문자열을 분할하는 것이다. (여기서 거의 포기했다.)

 

문자열을 분할하려면, 나머지 부분을 네 개로 쪼개어야 하는데 나머지 부분이 길이가 일정하지 않다.

결국에는 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만들던가, 필요한 만큼 가져다쓰던가 하는 방법이 있다.

 

길이를 반환할 경우 결국 비슷한 일을 하는 두 개의 함수를 각각 작성해야한다. 

필요한만큼 가져다쓰는 방법은, 함수에 s자체를 통째로 전달하는게 아닌, 필요한 만큼 가져다 쓰는 방법이다. 따라서 포인터를 옮기면 된다. 

 

2. 압축을 다 풀지 않고 뒤집는 방법

내가 고민했던게 종만북 풀이를 보고 바로 해결됐다.

 

사실, 뒤집은 결과는 검은색이나 흰색이나 원래 그림과 똑같다. 아니, 검은색이나 흰색을 뒤집으면 그 칸은 그칸 그대로다. 그런데 섞여있는 칸만 약간 달라졌을 뿐이다!

 

그래서 한가지 색이 아닌 경우에 재귀를 활용해 네 부분을 각각 상하로 뒤집은뒤 그 결과를 가지고와 이들을 병합하는 것이 맞았다.

 

그냥 4분할을 하고 각각을 뒤집은후 순서를 바꾸면 되는 문제였다. 

 

따라서 아래와 같은 코드를 도출할 수 있다.

string reserse_(string::iterator &it) {
    char head = *it;
    ++it;
    if (head == 'b' || head == 'w') {
        return string(1, head);
    }
    string upperLeft = reserse_(it);
    string upperRight = reserse_(it);
    string lowerLeft = reserse_(it);
    string lowerRight = reserse_(it);
    
    // 위와 아래 조각 위치를 바꿔서 리턴한다.
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

 

시간복잡도의 경우, 위 함수는 한번 호출될 때마다 한글자씩을 사용하기 때문에 결국에 문자열의 길이와 비례하므로 O(n)이 된다.

 

감상

분할정복 문제를 본격적으로 공부해본 적은 처음이라 당황스럽기도 하고, 약간 앞서 공부한 브루트포싱과 사뭇 다른 느낌이 든다. 

 

브루트포싱도 분할정복도 두가지 모두 재귀호출을 사용하지만, 브루트포싱의 경우에는 일부 하나의 조각에서 점점 답에 가까워지는 느낌이라면 분할정복의 경우에는 문제를 비슷한 사이즈로 나누고 그 답을 조합하는 것도 생각해내야한다. 따라서 브루트포싱 문제에 비해서는 조금 더 생각하고 파악할 시간이 필요한 것 같다.

 

문제를 분할할 사이즈를 알아야하고, 기저사례에 대해서도 깔끔하게 도출해낼 줄 알아야 할 것 같고, 분할한 결과를 어떻게 할 것인지에 대해서도 생각하는 경험이 많아진다면 이 유형 또한 익숙해지지 않을까 싶다.