[Algorithm] 쿼드트리 개념 및 코드

 

📌 쿼드트리란 무엇인가?

 

이진트리에 대해선 들어보셨을 겁니다.

한 개의 부모 노드에서 두 개의 자식 노드가 파생되는 구조의 자료구조입니다.

파이썬으로 구현하면 이렇게 생겼습니다.

 

🎨 이진 트리 구현 (python)

class Node:
	def __init__(self):
    	self.item = item
        self.left = None
        self.right = None

 

쿼드트리는 이진트리의 응용 버전입니다.

한 개의 부모 노드에서 네 개의 자식 노드가 파생되는 구조가 쿼드트리입니다.

쿼드트리는 이진트리처럼 나무가지로 표현할 수도 있습니다. 

 

 

 

 

📌 쿼드트리 정의

 

하. 지. 만 쿼드트리는 3D 데이터를 표현하기 위한 자료구조인 '장면 그래프(Scene Graph)'에 해당합니다. 상하 개념이 없고, 3차원 세계를 4개의 평면으로 분할합니다. 이런 특성으로 지형(Terrain) 문제에 사용됩니다.

 

정리하자면, 쿼드트리는 공간을 재귀적인 호출을 통해 4개의 자식 노드로 분할하는 방법이라고 할 수 있습니다. 그림을 보며 설명드리겠습니다.

 

밑의 네모는 영희의 영토입니다. 영희는 농사를 짓기 위해 잡초를 뽑아야 합니다. 하지만 이 넓은 영토를 모두 제초하는 것은 비효율적입니다. 그래서 영희는 (1) 해당 영토를 4 분할하고, 각각의 영토에 잡초가 있는지 확인합니다. 없으면 4 분할을 멈추고, 만약 잡초가 있는 영토는 (2) 또다시 4분할을 하기로 했습니다. (3) 이렇게 해서 마지막까지 잡초가 남아있는 영토들만 제초를 하고자 합니다.

 

 

 

영희는 첫 번째 4 분할을 했습니다. 그 결과, 왼쪽 상단의 영토에만 잡초가 있는 것이 확인되었습니다.

 

 

 

 

영희는 두 번째 4 분할을 했습니다(왼쪽). 그 결과, 왼쪽 상단의 영토에 또다시 존재했습니다. 세 번째 4 분할을 진행했습니다.(오른쪽) 잡초만 있는 영토가 2개 나왔습니다. 왼쪽 하단과 오른쪽 하단입니다. 쿼드트리 방식으로 문제에 접근한 덕분에 영희는 제초 범위를 효과적으로 줄일 수 있었습니다.

 

 

 

 

 

🎨 위의 과정을 파이썬으로 나타낸다면 어떨까요?

바닐라 파이썬으로 구현해보겠습니다.

 

잡초 영역 개수 = 0

def split(영토):
	# 영토에 잡초있는지 확인
    if 영토 전체가 잡초라면?:
       	잡초 영역 개수 += 1
        return None
    elif 영토에 잡초가 아예 없다면?:
    	return None
    else:
    	split(영토의 왼쪽 상단)
        split(영토의 왼쪽 하단)
       	split(영토의 오른쪽 상단)
        split(영토의 오른쪽 하단)


print(f"잡초가 있는 영역의 수 : {잡초 영역 개수}")

공간을 4 분할함과 동시에 재귀 함수를 이용하여 계속 트리가 뻗어나갈 수 있도록 설계해야 합니다. 

 

 

 

쿼드트리는 공간 분할에 쓰이는 알고리즘임을 배웠습니다. 구현에 있어서 재귀 함수를 활용해야 함도 배웠습니다. 이제 관련 문제를 풀어보신다면 훨씬 더 쉽게 와닿으실 겁니다.

 

 

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

[해설]

https://mengu.tistory.com/94?category=931464