[종만북] - 쿼드 트리 뒤집기(분할정복)

문제

접근방법

iterator를 쓰기 때문에, 

함수가 하나 끝나고 나서도 자연스럽게

it변수를 그대로 받아 쓸 수 있다.

 

it은 마지막으로 끝난 함수에서 검사한 위치 다음을 가리킨다. 

코드

,

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)

int C;

string reverse(string::iterator& it) {
    char head = *it;
    ++it;
    if(head == 'b' || head == 'w') return string(1, head);

    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);
    //각각 위와 아래 조각들의 위치를 바꾼다.
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}


int main() {

    cin >> C;
    while(C--) {
        string quadtree;
        cin >> quadtree;
        string::iterator it = quadtree.begin();
        string answer = reverse(it);
        cout << answer << endl;
    }

    return 0;
}

개선할 점

분할: 4개로 분할.

기저사례: b 또는 w를 만난경우.

병합: 4개의 함수로부터 받은 알파벳을 병합.

 

분할정복은 위 세개만 생각하면 된다.

어떻게 분할할지, 기저사례는 무엇일지, 병합은 어떻게 해야할지.

기저사례와 병합이 어렵다.