[Algorithm] QuadTree 공간 분할

쿼드트리 (Quadtree)

• 자식 노드가 4개인 트리를 의미한다.
• 게임에서는 일반적으로 2차원 지형 정보를 저장하는 데에 사용된다.
• 컬링을 위한 지형 검색에 쿼드 트리를 사용한다. 쿼드 트리를 이용하면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있기 때문이다.
• 쿼드트리를 사용하면 LOD(Level of details)를 구현하기 쉽다는 장점이 있다.

백준 1992번: 쿼드트리

#include <iostream>
using namespace std;

int arr[64][64];
int num;

bool Test(int x, int y, int size)
{
	int firstNum = arr[y][x];

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (arr[y + i][x + j] != firstNum)
			{
				return false;
			}
		}
	}
	cout << firstNum;

	return true;
}

void QuadTree(int x, int y, int size)
{
	if (!Test(x, y, size))
	{
		cout << "(";

		int half_size = size / 2;
		QuadTree(x, y, half_size);
		QuadTree(x + half_size, y, half_size);
		QuadTree(x, y + half_size, half_size);
		QuadTree(x + half_size, y + half_size, half_size);

		cout << ")";
	}
}

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

	cin >> num;

	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < num; j++)
		{
			char temp;
			cin >> temp;
			arr[i][j] = temp - '0';
		}
	}

	QuadTree(0, 0, num);

	return 0;
}

프로그래머스: 쿼드압축 후 개수 세기

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

int count0 = 0;
int count1 = 0;
int num;

bool Test(vector<vector<int>>& arr, int x, int y, int size)
{
    int firstNum = arr[y][x];

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (arr[y + i][x + j] != firstNum)
            {
                return false;
            }
        }
    }
    (firstNum == 0) ? count0++ : count1++;
    return true;
}

void QuadTree(vector<vector<int>>& arr, int x, int y, int size)
{
    if (!Test(arr, x, y, size))
    {
        int half_size = size / 2;
        QuadTree(arr, x, y, half_size);
        QuadTree(arr, x + half_size, y, half_size);
        QuadTree(arr, x, y + half_size, half_size);
        QuadTree(arr, x + half_size, y + half_size, half_size);
    }
}

vector<int> solution(vector<vector<int>> arr)
{
    QuadTree(arr, 0, 0, arr.size());
    vector<int> answer;
    answer.push_back(count0);
    answer.push_back(count1);

    return answer;
}