분할 정복 - 쿼드 트리 뒤집기

 

문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/QUADTREE

 

 

 

 

이것에 중점을 둬보자.

- 분할하고, 정복한다.

- 재귀 던져준 후에는 생각말자.

 

 

 

절차

- 트리를 입력 받는다. (string)

- 입력을 분석 (분할)

- 트리를 상하로 뒤집어서 출력

 

 

 

일단 입력을 받고 분할해보자.

아직 분할정복이 감이 안잡혔다. 문제를 보고 분할정복해야지 라는 생각을 못함. 일단 공부하는 부분이 분할정복이라서 어떻게 분할할지 생각해보자.

 

string tree를 입력받는다.

w나 b이면 return w, b; -> 기저사례

x이면 4개로 분할 -> 4개의 재귀로 들어감.

분할했으면 정복?병합?해결?도 하자.

 

순서는 왼쪽위 - 오른쪽위 - 왼쪽아래 - 오른쪽아래

뒤집으면 왼쪽아래 - 오른쪽아래 - 왼쪽위 - 오른쪽위

 

 

 

#include <iostream>
#include <string>
 
using namespace std;
 
string func(string s) {
    string current;
    int size = s.size();
 
    // 현재 tree
    current = s;
 
    // 기저사례
    if (current[0] == 'w') return "w";
    if (current[0] == 'b') return "b";
 
    int n = 0;
 
    // 왼쪽위
    n++;
    current = s.substr(n, size);
    string lu = func(current);
    // 오른쪽위
    n += lu.length(); // 왼쪽위 다음 문자열부터
    current = s.substr(n, size);
    string ru = func(current);
    // 왼쪽아래
    n += ru.length();
    current = s.substr(n, size);
    string ld = func(current);
    // 오른쪽아래
    n += ld.length();
    current = s.substr(n, size);
    string rd = func(current);
 
    // 정복? 병합? 해결?
    return "x" + ld + rd + lu + ru;
}
 
int main() {
    cin.sync_with_stdio(false);
    
    int T;
    string tree;
    cin >> T;
 
    for (int i = 0; i < T; ++i) {
        cin >> tree;
        cout << func(tree) << "\n";
    }
}