알고스팟 쿼드 트리 뒤집기

 

https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

 

 

<접근방법>

압축을 풀어서 뒤집고 다시 압축하는 방법은 불가능하다.

그림의 최대 크기가 2^20 * 2^20 이기 때문이다.

그렇다면 읽으면서 바로 뒤집어줘야한다.

 

그럼 뒤집는 것이 무엇인가 한 번 보자.

1. 더 이상의 새끼사각형이 없는 사각형에서 뒤집는 것은 위와 아래를 바꿔주는 것이다.

2. 새끼사각형이 있는 사각형에서는 새끼사각형을 뒤집어준 다음 위, 아래를 바꿔주는 것이다.

 

즉, 새끼사각형이 있으면 없을 때까지 뒤집어주면 된다.

여기에서 재귀로 풀면 되겠다는 아이디어를 얻을 수 있다.

 

이 때 입력string에 대한 반복자를 계속 전진시켜주는 것이 중요하다.

책에서는 string::iterator를 활용하여 구현하였다.

 

 

 

<시간 복잡도>

함수 1호출당  문자열 길이 1만큼 사용.

따라서 함수가 호출되는 횟수는 문자열의 길이에 비례하므로 O(n)이 된다.

 

 

 

 

<코드>

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

int tc;

string reverse(string::iterator &it) {
	char head = *it;
	++it;

	if (head == 'b' || head == 'w')
		//head 1개 출력
		return string(1, head);

	string square0 = reverse(it);
	string square1 = reverse(it);
	string square2 = reverse(it);
	string square3 = reverse(it);

	return string("x") + square2 + square3 + square0 + square1;
}

int main() {
	cin >> tc;

	while (tc--) {
		string str;
		cin >> str;

		string::iterator it = str.begin();

		cout << reverse(it) << '\n';
	}
	return 0;
}