[C++]algospot QUADTREE

문제 링크 : https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

문제

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

• 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.
• 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
• 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은 xwwwb로 압축됩니다.

그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

입력

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

출력

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

예제

입력	출력
4 w xbwwb xbwxwbbwb xxwwwbxwxwbbbwwxxxwwbbbwwwwbb	w xwbbw xxbwwbbbw xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

 

문제 풀이

• 분할 정복
• 현재 문자가 'x'일 경우 : 재귀 호출을 통해 네 부분의 결과를 얻은 후 각각 위와 아래 조각들의 위치를 바꾼 문자열을 반환
• 현재 문자가 'b' 혹은 'w'일 경우 : 현재 문자를 반환

내가 헤맸던 부분

재귀 호출로 문제를 풀 되, 아래의 조각들을 먼저 재귀 호출하여 출력하려 했기 때문에 위의 조각들을 나타내는 문자열에서 x가 존재할 경우 아래의 조각들을 몇번째 문자열의 몇번째 인덱스부터 호출해야하는지를 생각하기가 복잡했다.

→ 책의 풀이 처럼 문자열의 앞에서부터 조각의 순서대로 재귀 호출을 진행하고 나중에 조각의 위아래를 반대로 합쳐 반환하게 되면 위의 문제를 생각할 필요 없다.

→ string의 iterator를 참조 형식으로 받아 함수의 파라미터로 사용하면 문자열의 인덱스를 일일히 체크할 필요가 없기 때문에 상당히 효율적인 방법이라고 생각했다. 

풀이 코드

// 분할 정복
// 8ms
#include <iostream>
#include <iterator>
using namespace std;

int C;
string image;

string Quadtree(string::iterator& it) {
	char head = *it;
	++it;
	if (head == 'b' || head == 'w') return string(1, head);

	string upL = Quadtree(it);
	string upR = Quadtree(it);
	string lowL = Quadtree(it);
	string lowR = Quadtree(it);

	return "x" + lowL + lowR + upL + upR;
}
int main() {
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> image;
		string::iterator start = image.begin();
		cout << Quadtree(start) << endl;

	}
}