[C++] 알고스팟/분할정복 - 쿼드 트리 뒤집기

문제 링크

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

algospot.com :: QUADTREE

 

흑, 백으로 표시된 쿼드트리를 상하로 반전하여 출력해주는 문제입니다.

쿼드트리는 4분할로 나눠져있는 정사각형의 형태로 분할된 정사각형도 마찬가지로 4분할로 나뉠 수 있습니다.

따라서 분할된 각 부분을 재귀호출하여 계산하고 마지막에 결과를 합칠 수 있습니다.

 

쿼드트리는 문자열로 표현이 되고 검은 색은 b, 흰 색은 w로 표시합니다.

그리고 큰사각형의 4 픽셀이 모두 같은 색이 아닐 경우에는 x로 시작하고 내부 색깔에 따라 이어집니다.

 

 

사각형의 전체 색깔이 같으면 해당 문자를 반환합니다.

그렇지않으면 사각형을 4분할하여 각 분할된 사각형을 다시 재귀호출하여 분할된 사각형의 전체 색깔이 같은지를 다시 확인합니다.

이러한 방식으로 사각형의 전체 색깔이 같을 때 까지 4분할로 재귀호출하고 색깔이 같으면 문자를 반환하여 합쳐야 합니다.

 

 

구현 코드

 

	#include <iostream>
	#include <string>
	using namespace std;
	//문자열의 반복자를 인자로 사용
	string reverse(string::iterator& it){
	char head = *it;
	++it;
	//문자열의 첫 문자가 b나 w인 경우(사각형의 색이 같은 경우) 문자 그대로 반환
	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(){
	string str;
	int _;
	cin >> _;
	while(_--){
	cin >> str;
	string::iterator it = str.begin();
	cout << reverse(it) << endl;
	}
	return 0;
	}

view raw quadtree.cpp hosted with ❤ by GitHub