[알고리즘] 쿼드트리(Quad Tree)란? + (백준 1992 쿼드트리)

트리의 자식 노드가 4개인 트리를 뜻하고 있다.

 

 3D 데이터를 표현하기 위한 자료구조를 '장면 그래프( Scene Graph )'라고 부르는데, 이도 역시 그에 포함된다.

장면 그래프( Scene Graph )에는 쿼드 트리 이외에도 이진트리(2)와 옥트리(8)가 존재한다.

말 그대로 이진트리는 자식노드가 2개, 옥트리는 자식 노드가 8개가 있는 트리를 의미한다.

 

쿼드 트리는 일반적으로 상하 개념이 없어서 3차원 세계를 4개의 평면으로 분할하지만,

옥트리는 4개로 분할한 쿼드트리에서 상하의 분할 평면으로 나누어 총 8개의 자식 노드를 갖게 된다.

 

일반적으로 지형( Terrain )에 사용된다.

 

정의 : 공간을 재귀적인 호출로(Recursive ) 4개의 자식 노드로 분할하는 방법 

 

지형으로 설명을 하자면

 

초기에 하나의 넓은 월드의 지형을 1/4 로 나눈다.

 

그렇게 나온 4개의 노드를 부모로서 다시 1/4로 각각을 나눈다.

 

그럼 초기 하나의 월드에는 현재 16개의 노드가 존재한다.

 

이런 식으로 재귀적인 호출을 통해 각 노드간의 간격이 1보다 작거나 같을 때까지 분할한다.

 

 

출처 : https://blog.naver.com/maelblood/20168518863

 

관련 알고리즘 문제  2개

 

www.acmicpc.net/problem/1992

1992번: 쿼드트리

해당 문제는 

왼쪽과 같은 그림을 오른쪽과 같이 표현하며 

 

이와 같이 4분할 해주고, 한번 더

 

이렇게 다시 나눠준 결과를

(0(0011)(0(0111)01)1)

이렇게 표현 해주고 있다.

왼쪽부터 0이 왼쪽위의 0이 16개로 나눠준 부분이고,

그 다음 괄호 0011 은 오른쪽 위에 0 4개 2칸/ 1 4개 칸이고,

그 다음 괄호 0(0111)01 은 왼쪽아래에 0 4개와 0 1 1 1 / 0 4개 / 1 4개를 표현했다.

마지막 괄호 안 1이 오른쪽 아래 1 16개로 나타내고 있다.

 

해당 문제에서는 입력 값이

2의 제곱수로 64까지만 제한하고 있다.  예제로 입력된 값은 해당 값으로 출력 된다.

 

풀이방법

#include <iostream>
#include <string>
using namespace std;

#define MAX 64
int arr[MAX][MAX];
void compress(int n, int y, int x)
{
	//기저 사례
	if (n == 1)
	{
		cout << arr[y][x];
		return;
	}
	bool bIsZero = true;
	bool bIsOne = true;

	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + n; j++)
		{
			if (arr[i][j]==1)
			{
				bIsZero = false;
			}
			else
			{
				bIsOne = false;
			}

			if (bIsZero == false && bIsOne == false)
			{
				break;
			}

		}

		if (bIsZero == false && bIsOne == false) //두개 다 섞여있다면
		{
			break; //바로 중단 
		}
	}



	if (bIsZero)
		cout << 0;
	else if (bIsOne)
		cout << 1;
	else
	{
		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 << ")";
	}
	return;

}



int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;



	string s;
	for (int i = 0; i < N; i++)
	{
		cin >> s;

		for (int j = 0; j < N; j++)
			arr[i][j] = s[j] - '0';
	}



	compress(N, 0, 0);

	cout << "\n";

	return 0;

}

 

 

 

 

 또 다른 문제

 

 

algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE