티스토리 뷰
https://algospot.com/judge/problem/read/QUADTREE
algospot.com :: QUADTREE
쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적
algospot.com
문자열을 가리키는 포인터를 하나씩 뒤로 옮겨가면서 재귀호출한다. 분할한 부분의 전체가 흰색이거나 검은색일 경우 뒤집어도 똑같은 패턴이므로 그대로 리턴한다. 그게 아니라면 다시 분할한다. 위와 아래 조각들이 바뀐 패턴이 최종 결과이다.
#include <iostream>
#include <string>
using namespace std;
string reverse(string::iterator& it)
{
char head=*it++;
if(head=='b' || head=='w')
return string(1,head);
string upperLeft=reverse(it);
string upperRight=reverse(it);
string lowerLeft=reverse(it);
string lowerRight=reverse(it);
return string("x")+lowerLeft+lowerRight+upperLeft+upperRight;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
auto iter=s.begin();
cout<<reverse(iter)<<'\n';
}
return 0;
}