예제: 쿼드 트리 뒤집기
문제
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(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
풀이
알고리즘 문제해결 전략 도서를 보면, 분할 정복(Divide & Conquer)라는 섹션에 있는 문제이다.
그 이름에서 알 수 있듯이, 쿼드 트리 뒤집기도 문제를 분할해서 풀 수 있다.
w w
w b위 사각형이 있다고 하자.
이를 상하로 뒤집으면
w b
w w가 된다.
이는 어떤 사각형을 상하로 뒤집으면 좌상, 우상, 좌하, 우하 인 사각형이 좌하, 우하, 좌상, 우상이 된다는 뜻이다.
즉, xwwwb 를 뒤집으면 xwbww가 된다.
따라서, string을 받으면 총 4개(좌상, 우상, 좌하, 우하)의 구역으로 나누어 (좌하, 우하, 좌상, 우상)으로 재구성하여 출력하는 방식을 취했다.
어려웠던것은 x가 섞여있기 때문에 구역을 나누는 것이었다.
필자는 string을 for문을 돌면서, x가 있을 경우 index 위치에 +4를 해주며 총 4구역으로 나누었다.
입력 문자열의 길이가 최대 1,000이기 때문에 그리 큰 무리는 아닐 것 같다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<string>
using namespace std;
void quadTree(const string& word) {
if (word.size() == 1) {
cout << word;
return;
}
int idx[4] = { 0 };
int count = 1;
int cnt = 0;
int idxCnt = 0;
for (int i = 1; i < word.size(); i++) {
cnt++;
if (count == cnt) {
idx[idxCnt] = i;
idxCnt++;
count = 1;
cnt = 0;
}
if (word[i] == 'x') count += 4;
}
cout << "x";
quadTree(word.substr(idx[2], idx[3] - idx[2]));
quadTree(word.substr(idx[3]));
quadTree(word.substr(idx[0], idx[1] - idx[0]));
quadTree(word.substr(idx[1], idx[2] - idx[1]));
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
string word;
cin >> word;
quadTree(word);
cout << endl;
}
return 0;
}풀이 후기
비록 난이도 하인 문제였지만 풀고나서 뿌듯😃 했는데, 풀이를 보고 다시 눈물을 흘렸다.😥
나는 for문을 돌며 구역을 나누었지만, 알고리즘 문제해결 풀이에서 나온 방법은, iterator를 사용하여 아주 간단하게 재귀함수로 풀어버리는 것이었다.
참.. 푸는 방법은 여러가지겠지만, 이렇게 번뜩이는 풀이방법들이 나오는 것 보면 대단하다. 나도 접신의 경지에 이르기까지 계속 정진!
