[알고스팟] 쿼드 트리 뒤집기

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • QUADTREE
  • 10000ms
  • 65536kb
  • 5776
  • 2760 (47%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

출력

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

예제 입력

4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

예제 출력

w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

어떻게 접근할까?

 

 위 문제는 어떻게 접근하면 좋을까요? 

 우선 문제를 파악해봅시다. 

 위 그림은 트리 형식으로 나타낼 수 있습니다. 노드로는 x, b, w가 들어갑니다.

 만약 x가 노드로 온다면, 또 다시 해당 영역을 4개로 나누는 자식노드가 생깁니다.

 즉, 재귀적인 형식으로 트리를 순회하여 표현할 수 있습니다.

 그렇다면 어떻게 해서 좌표 데이터의 상하를 바꿀 수 있을까요?

 그림을 통해 확인해 봅시다.

 

트리 형식이 위와 같다고 하겠습니다.

각 영역의 상하를 변경합니다.

마지막으로 현재 영역의 위 아래를 바꿔주면 전체적으로 영역의 상하가 바뀐 것을 볼 수 있습니다!

작은 영역을 뒤집고 이를 이용해 큰 영역을 뒤집을 수 있습니다. 

따라서 분할 정복 방법을 통해 작은 부분들을 뒤집고, 큰 부분을 점차 뒤집는 방법을 사용하겠습니다.

그렇다면 재귀를 이용하여 이를 구현한다면 기저 사례가 되는 부분은 어디일까요?

바로, b나 w로 트리가 끝나는 지점입니다. 

모든 영역이 검은색이거나 하얀색이라면 상하를 뒤집어도 똑같기 때문입니다.  

또한, 재귀 함수를 이용할 때 가장 힘든 것이 

이전 재귀 함수를 빠져나왔을 때 다음에 살펴봐야하는 노드에 들어가야하는 단어의 위치가 어디인지 알기 힘들다는 것입니다.

따라서, 레퍼런스를 이용해서 현재 자신이 읽고 있는 곳이 어디인지 항상 전해주도록 하겠습니다.

이렇게 하면 재귀 함수를 빠져나왔을 때 다음에 살펴봐야하는 곳을 쉽게 알 수 있을 것입니다.

코드

//쿼드 트리 뒤집기
//알고스팟
//https://algospot.com/judge/problem/read/QUADTREE
#include<stdio.h>
 
enum datas {W = 'w', B = 'b', X = 'x'};
 
char str[1001];
 
struct QUAD
{
    QUAD* quads[4];
    char c;
 
    void print()
    {
        if (c == X)
        {
            printf("x");
            for (int i = 0; i < 4; i++)
            {
                quads[i]->print();
            }
        }
        else
        {
            printf("%c", c);
        }
    }
} ;
 
QUAD quads[1000];
int idx = 0;
 
QUAD* makeQuad(char* str, int &len)
{
    if (str[len] == X)
    {        
        len++;
        int p = idx++;
        quads[p].quads[0] = makeQuad(str, len);
        quads[p].quads[1] = makeQuad(str, len);
        quads[p].quads[2] = makeQuad(str, len);
        quads[p].quads[3] = makeQuad(str, len);
 
        quads[p].c = X;
 
        return &quads[p];
    }
 
    else
    {
        quads[idx].c = str[len];
        len++;
 
        return &quads[idx++];
    }
}
 
void reverseQUAD(QUAD* quad)
{
    if (quad->c == X)
    {
        for (int i = 0; i < 4; i++)
        {
            reverseQUAD(quad->quads[i]);
        }
 
        QUAD *t1 = quad->quads[0], *t2 = quad->quads[1];
        quad->quads[0] = quad->quads[2];
        quad->quads[1] = quad->quads[3];
        quad->quads[2] = t1;
        quad->quads[3] = t2;
    }
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        scanf("%s\n", str);
        idx = 0;
        
        QUAD* res;
        int len = 0;
 
        res = makeQuad(str, len);
 
        reverseQUAD(res);
 
        res->print();
        printf("\n");
    }
 
    return 0;
}