[알고스팟/C,C++] QUADTREE: 쿼드 트리 뒤집기

www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

처음에 입력값을 제대로 보지 않고 풀었는데, 들어올 수 있는 입력값이 $2^{20}\times 2^{20}$ 으로 매우 큰 수 입니다.

 

최초 시도는 입력값을 16 x 16 크기의 배열 형태로 변환하고,

 

그것을 뒤집은 뒤, 다시 압축하였습니다.

 

당연히 결과는 오답입니다. 쿼드 트리의 크기가 16 x 16으로 고정이 아닐뿐더러,

 

해당 방법으로는 시간이 초과하게 됩니다 ㅜㅜ..

 

 

결국 힌트를 얻어 다시 풀게 되었는데, 기본 풀이 방법은 입력값을 2차원 배열 형태로 만들지 않아도

 

뒤집을 수 있다는 것입니다.

 

 

예제 입력을 예로 들어, xbwxwbbwb 가 있다면, x{b}{w}{xwbbw}{b} 로 나타낼 수 있겠죠!

 

각각 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래에 해당하는 값입니다.

 

그림을 상하 반전시켜야 하기때문에..

 

왼쪽 위와 왼쪽 아래를 바꿔주고 오른쪽 위와 오른쪽 아래를 바꿔주면 되는 것이죠.

 

순서로 보면 이렇습니다.

 

xbwxwbbwb → x{b}{w}{x{w}{b}{b}{w}}{b} → x{b}{w}{x{b}{w}{w}{b}}{b} → x{x{b}{w}{w}{b}}{b}{b}{w} → xxbwwbbbw

 

#include<iostream>

using namespace std;

string s;
int r;

string reverse()
{
    string tmp = "";
    tmp = tmp + s[r];
    r++;
    if (tmp == "w" || tmp == "b") {
        return tmp;
    }

    string top_left = reverse();
    string top_right = reverse();
    string bot_left = reverse();
    string bot_right = reverse();

    return "x" + bot_left + bot_right + top_left + top_right;
}

int main(void)
{
    int c; cin >> c;
    
    for (int i = 0; i < c; i++) {
        cin >> s;
        r = 0;
        cout << reverse() << "\n";
    }

    return 0;
}

 

아래는 처음 시도했던 방법입니다.

 

#include<iostream>

using namespace std;

const int MAX = 16;

string s;
int r;

char quad[MAX][MAX];

void decom(int y, int x, int len)
{
    int half = len / 2;
    for (int q = 0; q < 4; q++) {
        r++;
        int y_loc = y + (q / 2 * len);
        int x_loc = x + (q % 2 * len);
        if (s[r] == 'x') decom(y_loc, x_loc, half);
        else {
            for (int i = y_loc; i < y_loc + len; i++) {
                for (int j = x_loc; j < x_loc + len; j++) {
                    quad[i][j] = s[r];
                }
            }
        }
    }
    return;
}

void reverse()
{
    for (int i = 0; i < MAX / 2; i++) {
        for (int j = 0; j < MAX; j++) {
            char tmp = quad[i][j];
            quad[i][j] = quad[MAX - 1 - i][j];
            quad[MAX - 1 - i][j] = tmp;
        }
    }
}

void com(int y, int x, int len)
{
    if (len == 0) return;
    int value = 0;
    for (int i = y; i < y + len; i++) {
        for (int j = x; j < x + len; j++) {
            if (quad[i][j] == 'w') value++;
            else value--;
        }
    }
    if (value == len * len) {
        cout << "w";
    }
    else if (value == len * len * -1) {
        cout << "b";
    }
    else {
        int half = len / 2;
        cout << "x";
        for (int q = 0; q < 4; q++) {
            int y_loc = y + (q / 2 * half);
            int x_loc = x + (q % 2 * half);
            com(y_loc, x_loc, half);
        }
    }
}

int main(void)
{
    int c; cin >> c;

    for (int i = 0; i < c; i++) {
        cin >> s;
        if (s[0] == 'x') {
            r = 0;
            decom(0, 0, 8);
            reverse();
            com(0, 0, 16);
            cout << "\n";
        }
        else if (s[0] == 'w') cout << "w\n";
        else cout << "b\n";
    }

    return 0;
}