[알고스팟] 쿼드트리 뒤집기 - 분할 정복, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

 

쿼드트리 뒤집기(링크)

접근 방법

문제에서는 원본의 흑백 그림에 대해 quad tree는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 순서로 알파벳 코드를 작성해 나간다. 윗줄과 아랫줄을 바꾼다고 할 때, 원본 그림에 대해 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위의 순서로 알파벳 코드를 작성하면 상하 반전이 된 quad tree를 얻을 수 있다. 

 

quad tree는 x를 만나면 4개의 알파벳 (4면의 그림) 을 만나게 되니까, 기본적으로 재귀 함수 형태로 작성했다. 재귀 함수의 인자로 문자열 자체를 넘겨 string.substr(1)을 통해 문자를 하나씩 줄여가는 방식을 취하려 했는데 재귀 내부에서의 변화를 함수 탈출 후에도 유지하는 방법이 떠오르지 않아 iterator를 사용하는 답안의 방식을 사용했다.

C++ 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Hand over the reference for the iterator as an argument so that
// you can retain the modifications inside of the recursion.
string reverseQuadTree(string::iterator& iter) {
    char letter = *iter; ++iter;
    // Base case: If the letter is not 'x', return the letter.
    if (letter == 'w' || letter == 'b') return string(1, letter);

    // If the letter is 'x', get into the recursion.
    // Task piece: Take one piece at the front from the quadTree string.
    string ret[4];
    ret[0] = reverseQuadTree(iter);
    ret[1] = reverseQuadTree(iter);
    ret[2] = reverseQuadTree(iter);
    ret[3] = reverseQuadTree(iter);

    return "x" + ret[2] + ret[3] + ret[0] + ret[1];
}

int main() {
    int C; cin >> C;
    string quadTree;
    vector<string> answers;

    while (C-- > 0) {
        cin >> quadTree;
        string::iterator iter = quadTree.begin();
        answers.push_back(reverseQuadTree(iter));
    }
    for (const auto& e: answers) cout << e << endl;

    return 0;
}