[분할 정복] QUADTREE

[1. 문제 재정의 및 추상화]

 

[2. 해결 계획]

 

[3. 계획 검증]

 

[4. 구현]

#include <iostream>
#include <cstring>
#include <cassert>

// 좌상단으로 계속 재귀적으로 들어가다보면, 
// 언젠가 b, w 를 만나게 됨
// 그 다음 문자가 우상단에 위치하는 것 이므로
// 참조자 형태로 offset 을 받아서 업데이트 해야 함.
std::string solve(const char quadtree[], int &offset)
{
    assert(offset < strlen(quadtree));
    const char head = quadtree[offset];
    // 다음 구역을 확인하기 위해
    // 먼저 offset 을 업데이트 함.
    offset++;

    if (head == 'b' || head == 'w')
    {
        const char buf[2] = {head, 0};
        return std::string(buf);
    }
    // 문제 입력 상
    // 문자열은 b 또는 w 로 끝나야 함.
    assert(head == 'x');
    
    const std::string &upLeft = solve(quadtree, offset);
    const std::string &upRight = solve(quadtree, offset);
    const std::string &downLeft = solve(quadtree, offset);
    const std::string &downRight = solve(quadtree, offset);

    // 이 구역에서 head 는 x 이므로
    // x 로 시작해야 함.
    // 여기서 상하 뒤집도록 함.
    return std::string("x") 
           + downLeft + downRight 
           + upLeft + upRight;
}


int main()
{
    int T;
    char buf[1024];

    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++)
    {
        memset(buf, 0, sizeof(buf));
        scanf("%s", buf);
        int offset = 0;
        printf("%s\n", solve(buf, offset).data());
    }

    return 0;
}