[자료구조] 쿼드 트리(Quad Tree)

쿼드 트리(Quad Tree)

• 트리 자료구조 중 하나로 부모 노드 아래에 자식 노드를 4개씩 가지고 있다.
• 이미지 용량, 충돌, 컬링 등 다양한 곳에서 최적화 기법으로 사용한다.
• 게임에서는 일반적으로 지형 정보를 저장하는 데에 사용된다.
  쿼드 트리를 이용하면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있다.

---

쿼드 트리 예시

흑백 영상의 데이터 압축하기

백준 1992번 : 쿼드트리 (https://www.acmicpc.net/problem/1992)

1. 가장 처음의 맵이 모두 흰색(0)이거나, 모두 검은색(1)이 아니기 때문에 압축할 수 없다.
   따라서, 맵을 4등분한다. (위의 그림에서 빨간색 라인)

2. 4등분된 맵에서 각각의 구간을 살펴보면, 왼쪽 위 구간은 모두 0이기 때문에 압축이 가능하다.
   따라서, 하나의 0으로 표현합니다.

3. 오른쪽 위 구간은 모두 흰색(0)이거나, 모두 검은색(1)이 아니기 때문에 압축할 수 없다.
   따라서, 맵을 다시 4등분합니다.

4. 모든 구간들을 계속 반복합니다.

쿼드 트리 구현

• 위 문제를 C++로 구현하면 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int map[65][65];

void compress(int n, int y, int x)
{
	if (n == 1)
	{
		cout << map[y][x];
		return;
	}
		 
	bool exist0 = false;
	bool exist1 = false;

	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + n; j++)
		{
			if (map[i][j] == 0)
				exist0 = true;
			else
				exist1 = true;

			if (exist0 && exist1)
				break;
		}
		if (exist0 && exist1)
			break;
	}

	if (exist0 && exist1)
	{
		cout << '(';
		compress(n / 2, y, x);					// 2사분면
		compress(n / 2, y, x + n / 2);			// 1사분면
		compress(n / 2, y + n / 2, x);			// 3사분면
		compress(n / 2, y + n / 2, x + n / 2);	// 4사분면
		cout << ')';
	}
	else if (exist0)
		cout << 0;
	else
		cout << 1;
}

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < n; j++)
		{
			map[i][j] = str[j] - '0';
		}
	}

	compress(n, 0, 0);
}

---

참고
https://velog.io/@doorbals_512/UNSEEN-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%EA%B2%8C%EC%9E%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://pangtrue.tistory.com/62