[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)

algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

<풀이>

1. 쿼드 트리로 압축된 문자열을 입력받는다.

2. 입력받은 쿼드 트리를 상하로 뒤집은 쿼드 트리를 출력한다.

 

<해법>

1. 쿼드 트리를 상하로 뒤집는 방법

=> 쿼드 트리를 상하로 뒤집었을 경우, 쿼드 트리의 순서는 x(아래 왼쪽)(아래 오른쪽)(위 왼쪽)(위 오른쪽)이 됩니다. 따라서, 압축된 쿼드 트리를 복원할 필요 없이, 각 부분의 압축된 문자열을 알아낸 후 위 순서에 따라 재배치를 해주면 됩니다.

 

#include <iostream>
#include <string>
 
using namespace std;
 
string str;
int pos;
string answer;
 
string quadtree() {
 
    char cur = str[pos++];
 
    //b나 w일 경우 해당 부분 완료
    if (cur == 'b' || cur == 'w') {
        return string(1, cur);
    }
 
    //4부분 나눠서 해결
    string upLeft = quadtree();
    string upRight = quadtree();
    string downLeft = quadtree();
    string downRight = quadtree();
 
    //상하로 뒤집었을 때의 순서
    return "x" + downLeft + downRight + upLeft + upRight;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        str = "";
        pos = 0;
        answer = "";
 
        //입력
        cin >> str;
 
        //해법
        answer = quadtree();
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}

 

분할 정복에 대해 알아볼 수 있는 문제였습니다.

---

아래 문제를 응용한 것이 위 문제라고 생각합니다. 아래 문제도 풀어보는 것도 도움이 될 것 같습니다!

www.acmicpc.net/problem/1992

1992번: 쿼드트리