[#2-3]분할정복-문제: 쿼드 트리 뒤집기(문제 ID: QUADTREE)

문제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include<iostream> #include<string> using namespace std; string reverse(string::iterator &it) {     char head = *it;     ++it;     if (head == 'b' || head == 'w') //전체가 블랙이라면 b, 전체가 화이트라면 w, 그렇기에 최소로 쪼개지는 단위이며 아닐시 다음 노드에 x로 출력하고 다시 분해         return string(1, head);     string upperLeft = reverse(it); // 위에서 왼쪽 자리 -> 밑에서 왼쪽 자리로     string upperRight = reverse(it); // 위에서 오른쪽 자리 -> 밑에서 오른쪽 자리로     string lowerLeft = reverse(it); // 아래에서 왼쪽 자리 -> 위에서 왼쪽 자리로     string lowerRight = reverse(it); // 아래에서 오른쪽 자리 -> 위에서 오른쪽 자리로     //주석에 설명한대로 위치를 바꿔서 리턴해주면 정답!(항상 먼저 분할하니까 맨 앞 x출력은 고정)     return string("x") + lowerLeft + lowerRight + upperLeft + upperRight; } int main(int argc, char *argv[]) {     int Testcase;     string input;     cin >> Testcase;     for (int i = 0; i < Testcase; i++)     {         cin >> input;         string::iterator it = input.begin();         cout << reverse(it) << endl;     }     return 0; } Colored by Color Scripter

cs

 

이 문제는 처음에 4등분을 한 뒤에 X가 아니라면 즉. Black 또는 White로 이루어져 있다면 더 이상의 분할을 멈추고 반환하는 것을 알고 이해하면 문제를 풀기 쉽다. 이후 마지막에 뒤집을 경우 바뀌는 위치를 return 할 때 적정 위치에 값을 주어 표현하였다.