QUADTREE

문제 링크

QUDTREE

문제 풀이

주어진 공간을 4개로 분할하여 재귀적으로 나타낸다. 따라서 입력 문자열을 4개씩 적절하게 나누어 재귀호출하여 계산한 다음, 4개의 답들을 합칠때, 순서만 바꿔준다.

구현

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

int TC, index;
string tree;

string solve() {
    char color = tree[index++];
    if (color == 'b') return "b";
    else if (color == 'w') return "w";

    string s1, s2, s3, s4;
    s1 = solve(); s2 = solve(); s3 = solve(); s4 = solve();
    return "x" + s3 + s4 + s1 + s2;
}

int main() {
    cin >> TC;
    while (TC--) {
        cin >> tree;
        index = 0;
        cout << solve() << "\n";
    }
    return 0;
}