링크 : https://algospot.com/judge/problem/read/QUADTREE
문제읽기
흰색과 검은 색으로 그림을 압축하는 것. 주어진 공간을 항상 4개로 분할하여 재귀적으로 풀어야 한다.
게다가 심지어 상하로 뒤집은 것을 결과로 내놔야 하는데 이거는 재귀로 가져오기 때문에 이런 조건을 친절하게 넣어준 것이 아닐까? -> 아니다. reverse 함수 만드는 연습하라고 넣은 것이다.
- 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
- 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작하여 최적화해 나가기
이렇게 두 가지 방법으로 접근해야 한다. 하지만 더 쉬운 것은 1번.
입력을 보자. 우리가 압축하는 것이 아니라 이미 압축되어 있는 그림의 문자열을 입력받아 압축을 풀어야 하는 것이다.
정리
base case : 문자열 s의 첫글자가 w나 b인 경우이다. 이때는 배열 전체에 해당하는 색을 칠하고 종료
general case : s의 나머지 부분을 넷으로 쪼개 재귀 호출한다. 배열의 어느 부분에 저장되어야 하는지 지정 위치 오프셋 또한 전달해야 한다.
구현
decompress() 함수에서 필요한 만큼 가져다 쓰도록 하는 것이 중요하다. s를 통째로 전달하는 것이 아니라 s의 한 글자를 가리키는 포인터를 전달해 한 글자를 검사할 때마다 포인터를 앞으로 한칸씩 옮기는 것이다. 따라서 함수가 종료하고 나면 반복자는 항상 다음 부분의 시작 위치를 가리키게 된다.
코드
#include<iostream>
#include<string>
using namespace std;
#define MAX_SIZE 20
char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(string::iterator& it, int y, int x, int size) {
//글자 하나를 탐색하면 iterator을 옮겨준다.
char head = *(it++);
if (head == 'b' || head == 'w') {
for (int dy = 0; dy < size; ++dy) {
for (int dx = 0; dx < size; ++dx) {
decompressed[y + dy][x + dx] = head;
}
}
}
else {
int half = size / 2;
decompress(it, y, x, half);
decompress(it, y, x+half, half);
decompress(it, y+half, x, half);
decompress(it, y+half, x+half, half);
}
}
string reverse(string::iterator& it) {
char head = *it;
++it;
if (head == 'w' || head == 'b')
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 C; string strIn;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> strIn;
if (strIn.size() > 1000) exit(-1);
string::iterator iter = strIn.begin();
//decompress(iter, 0, 0, strIn.length());
//iter = strIn.begin();
cout << reverse(iter) << endl;
}
return 0;
}
분석
아. 거의 앞까지 갔는데 다 놓친게 되었다. decompress는 안쓰였다. reverse만 쓰였다. 우선 재귀함수 공부라는데 큰 의의를 두고 넘어간다.
🛰️ 2021 fall ~