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

문제 링크

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

algospot.com :: QUADTREE

 

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

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

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

 

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

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

 

 

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

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

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

 

 

구현 코드