QUADTREE (중하, p. 189)

사실 문제에서 Tree모양을 안보여주고, 문제 이름에서도 트리라는 이름을 빼면 조금 더 어려워질 수 있겠다는 생각이 듦.

압축된 형태가 Tree 자료구조를 갖고, 각각의 노드는 자식노드가 아예 없거나 아니면 4개의 자식노드를 갖는 독특한 구조가 됨. 이를 문자열을 가지고 Tree를 표현한 뒤, 문제의 요구사항에 맞게 Tree를 재탐색하면 답을 구할 수 있음.

앞에서 난이도 ‘하’였던 문제보다는 조금 어렵기 때문에, 책에선 난이도 ‘하’로 책정되어있었지만, 나는 ‘중하’를 부여함.

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
void Init(const string & s) {
    v.clear();
    v.resize(s.size()+1, vector<int>());
}
string s;
int MakeTree(int x) {
    int nx = x+1;
    if(s[x] == 'x') { //v[x]
        for(int i = 0; i < 4; i++) {
            v[x].push_back(nx);
            nx = MakeTree(nx);
        }
    }
    return nx;
}
int trans[] = {2,3,0,1};
void Dfs(int x) {
    printf("%c", s[x]);
    if(v[x].empty()) return;
    for(int i=0; i<4; i++) {
        int nx = v[x][trans[i]];
        Dfs(nx);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> s;
        Init(s);
        MakeTree(0);
        Dfs(0);
        puts("");
    }
    return 0;
}