[알고스팟] QUADTREE 쿼드트리 뒤집기

문제

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

입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 220 × 220 을 넘지 않습니다.

출력
각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

예제 입력
4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

예제 출력
w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

concept

압축을 해제하여 뒤집고 다시 압축을 진행하기엔 소요가 많으므로, 입력값을 직접적으로 이용하여 출력을 뽑아내도록 한다. 재귀적으로 깊게 탐색하는 것이 자명해 보인다.

code

1) iterator 라이브러리 이용

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



string turn(string::iterator& it) {
	char head = *it;
	it++;
	if (head == 'b' || head == 'w') return string(1, head);
	else {
		string first = turn(it);
		string second = turn(it);
		string third = turn(it);
		string fourth = turn(it);
		return string("x") + third + fourth+first+second;
	}
}

int main() {
	int c;
	cin >> c;
	string sentence;
	for (int i = 0; i < c; i++) {
		cin >> sentence;
		string::iterator iter = sentence.begin();
		cout << turn(iter)<<endl;
	}
	
}

2) iterator를 전역변수를 이용, 직접 구현

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

string sentence;
int iter=0;

string turn() {
	char head = sentence[iter];
	iter++;
	
	if (head == 'b' || head == 'w') {
		string tmp(1, head);
		return tmp;
	}
	else {
		string first = turn();
		string second = turn();
		string third = turn();
		string fourth = turn();
		return "x" + third + fourth+first+second;
	}
}

int main() {
	int c;
	cin >> c;
	
	for (int i = 0; i < c; i++) {
		cin >> sentence;
		cout << turn()<<endl;
		iter = 0;
	}
	
}

comment

string(처음엔 벡터로 접근) 리턴과, x 발견시 x에 의한 그룹에 해당하는 index를 어떻게 동시에 리턴시킬 것인가에서 막혔다. iterator 라이브러리를 이용하는 방법과, 직접 전역변수로 iterator를 구현하는 방법 2가지로 접근이 가능했다. iterator를 처음 접해 어려움이 있었으며, 아직 미숙한 string에 대한 drill이 필요해보인다.