[ALGOSPOT] QUADTREE

출처 : 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가 됩니다.

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

 

<입력>

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 220 × 220 을 넘지 않습니다.

<출력>

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

 

<아이디어>

x를 기준으로 나누는데, 좌상, 우상, 좌하, 우하 구간 중 한 구간을 만들게 되면 그 구간을 stack에 넣는다.

그렇게 하면 현재 x에서 stack 4개를 뽑으면 그 구간을 4등분한 구간들의 정보를 알 수 있다.

4등분한 구간string을 [1][2][3][4] -> [3][4][1][2]로 바꾼 뒤, 다시 stack에 넣는다.

반복하면 맨 마지막에 stack에는 완성된 string 하나만 남게된다.

 

<구현>

분할정복 + stack 으로 구현했습니다.

base case : string의 현재 위치(pos)가  'x'가 아닌경우 -> 해당 문자("w" 또는 "b") 를 stack에 쌓습니다.

stack에 들어있는 문자열을 하나씩 뽑아 상하로 뒤집은 것처럼 string을 만들어 stack에 넣습니다.

([1][2][3][4] -> [3][4][1][2])

재귀함수가 끝나면 stack에 한 string만 남게되는데, 이 string이 완성된 string입니다.

 

<실수한 부분>

string의 현재위치를 표현하고 싶은데 함수 내에서 해결하려다 많이 헤매었습니다.

결국 전역변수에 pos를 선언함으로써 문제를 해결했습니다.

 

string의 현재위치는 0부터 string.length()-1까지 순서대로 움직이기 때문에, 전역변수로 사용해도 큰 문제가 일어나지 않습니다.

오히려 함수 안에서 해결하려고 하니까 함수에서 상위 함수로 pos의 변동을 알려줘야하는데 적절한 방법이 생각나지 않더군요(ㅜㅜ)

지금까지 string이랑 stack을 call by reference로 했으면서 int형인 pos를 call by reference로 하면 되는건데 이게 생각이 안났네요

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int pos;
 
void divs(string& s, stack<string>& st)
{
    string ptmp = "";
    if(s[pos]!='x')
    {
        st.push(ptmp+s[pos++]);
        return;
    }
    pos++;
    ptmp += 'x';
    int cnt = 0;
    while(cnt<4 && pos<s.length())
    {
        divs(s, st);
        cnt++;
    }
    string tmp[4];
    while(cnt>0)
    {
        tmp[--cnt] = st.top();
        st.pop();
    }
    st.push(ptmp+tmp[2]+tmp[3]+tmp[0]+tmp[1]);
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        string s;
        cin>>s;
        pos = 0;
        stack<string> st;
        divs(s, st);
        cout<<st.top()<<endl;
    }
    return 0;
}

 

 

다음은 책을 참고하여 수정한 코드입니다.

 

#include <bits/stdc++.h>
#include <string>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
string updown(int& pos, string& s)
{
    char head = s[pos++];
    if(head!='x') return string(1, head);
    string tmp[4];
    for(int i=0;i<4;i++)
        tmp[i] = updown(pos, s);
    return string("x") + tmp[2]+tmp[3]+tmp[0]+tmp[1];
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        string s;
        cin>>s;
        int pos = 0;
        cout<<updown(pos, s)<<endl;
    }
    return 0;
}