[분할과 정복] 쿼드 트리 뒤집기(문제 ID:QUADTREE, 난이도:하)

1. 문제정의

 

 

 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(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 을 넘지 않습니다.

출력

각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

---

2. 문제 설계

사이즈가 작으면 압축을 풀고, 반전하고, 다시 압축 순으로 풀 수 있지만, 거대한 그림에는 엄청난 메모리 낭비가 될 수 있다. 그래서 분활과 정복을 이용하여 모두 압축을 해제하지 않아도 반전된 결과를 쿼드트리로 표한할 수 있다. 결과 이미지를 뒤집은 결과를 재귀 호출을 이용해 코드를 만들어 봅시다.

부분 문제 정의입력 스트링을 읽어 전체가 흰색이나 검은색은 뒤집어도 같다. 그래서 'B', 'W'를 만나면 그대로 해당 색을 반환해주면 된다. 하지만 'X'를 만나는 경우 재귀를 이용하여 상하반전을 실시한다.

---

3. 구현

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

//쿼드 트리 뒤집기 문제를 해결하는 분할 정복 알고리즘
string reverse(string::iterator &it){
  char head = *(it++);
        //기저 사례: 1번 혹은 2번 과정일 경우
        if (head == 'b' || head == 'w')
               return string(1, head);

        //분할 : 'x' 경우 각 사분면도 반전 실시
        string upperLeft = reverse(it); //1사분면
        string upperRight = reverse(it); //2사분면
        string lowerLeft = reverse(it); //3사분면
        string lowerRight = reverse(it); //4사분면

        //정복 : 분할된 문제들을 하나로 합침(3-4-1-2 순)
        return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

int main(void){
        int test_case;
        string picture;
        cin >> test_case;
        if (test_case < 0 || test_case>50)
               return 0;

        for (int i = 0; i < test_case; i++){

               cin >> picture;
               if (picture.size() > 100)
                       return 0;
       
               string::iterator it = picture.begin();
               cout <<"OUTPUT : "<< reverse(it) << endl;
        }
        return 0;
}

4. 테스트

 

 

출처 : https://algospot.com/judge/problem/read/QUADTREE