1. 쿼드 트리

• 트리 자료구조 중 하나로 부모 노드 아래에 자식 노드를 4개씩 가지고 있음
• 이미지 용량, 충돌, 컬링 등 다양한 곳에서 최적화 기법으로 사용

2. 알고리즘

쿼드 트리를 사용해 흑백 이미지를 압축해보자

1) 초기상태

2) 압축결과

(0(1101)1((0011)(0111)1(1110)))

• 이미지의 구역을 4개로 나눈 후, 같은 숫자로 구성된 부분을 하나로 묶고 그렇지 않다면 다시 구역은 4개로 나누는 형태
  

3. 소스코드

#include<string>
#include<vector>
#include<iostream>

using namespace std;

vector<string> v;

void func(int n, int y, int x)
{
	char c = v[y][x];

	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (v[i][j] != c) {
				cout << '(';
				func(n / 2, y, x);
				func(n / 2, y, x+ n / 2);
				func(n / 2, y+ n / 2, x);
				func(n / 2, y+ n / 2, x+ n / 2);
				cout << ')';
				return;
			}
		}
	}
	cout << c;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N,n;
	cin >> N;
	n = N;
	while (n--)
	{
		string s;
		cin >> s;
		v.push_back(s);
	}

	func(N, 0, 0);

	return 0;
}