Unity | BFS(너비우선 탐색) 와 DFS(깊이우선 탐색)

 

< BFS(Breadth-First Search, 너비 우선 탐색) >

 

 

1. BFS의 개념과 작동 원리

BFS는 "가까운 곳부터 전부 확인"하는 전략, 왼쪽부터 탐색을 시작.

• 자료구조: **큐(Queue)**를 사용함 (선입선출, FIFO).
• Unity 활용 사례:
  • 최단 경로 탐색: 가중치가 없는 그래프(예: 타일 기반 맵)에서 최단 거리를 찾을 때 사용함.
  • 범위 탐색: 유닛의 이동 가능 범위 표시, 폭발 영향 범위 계산.
  • NavMesh: 내부적으로 경로를 계산할 때 노드 기반 탐색의 기초가 됨.

 

 

 

2. 장점과 단점

구분	내용
장점	1. 최단 경로 보장: 가중치가 없는 그래프에서 처음 발견한 해가 반드시 최단 경로임. 2. 무한 루프 방지: 노드 깊이가 무한해도 목표가 근처에 있다면 반드시 찾음.
단점	1. 메모리 소모: 큐에 많은 노드를 저장해야 하므로 공간 복잡도가 높음. 2. 비효율적 탐색: 목표가 깊은 곳에 있다면 모든 너비를 다 뒤져야 하므로 느려짐.

 

---

< DFS(Depth-First Search, 깊이 우선 탐색) >

 

 

1. DFS의 개념과 작동 원리

DFS는 현재 노드에서 연결된 인접 노드 중 하나를 선택해 최대한 깊게 파고들며 탐색함. 더 이상 갈 곳이 없으면 마지막 갈림길로 돌아와서(Backtracking) 다른 경로를 탐색함.

• 자료구조: 주로 **스택(Stack)**을 사용하거나 **재귀 호출(Recursion)**을 통해 구현함.
• Unity 활용 사례: * 계층 구조(Hierarchy)의 특정 자식 오브젝트 검색.
  • 절차적 맵 생성 시 미로(Maze) 생성 알고리즘.
  • 퍼즐 게임의 상태 트리 탐색.

 

 

2. 장점과 단점

구분	내용
장점	1. 메모리 효율: 현재 경로의 노드들만 저장하면 되므로 BFS보다 메모리 점유율이 낮음 ($O(d)$, $d$는 깊이). 2. 깊은 해 탐색: 목표 노드가 깊은 곳에 있을 경우 매우 빠르게 찾음.
단점	1. 무한 루프 위험: 사이클이 있는 그래프에서 방문 처리를 안 하면 무한 루프에 빠짐. 2. 최단 경로 불확실: 처음 발견한 해가 최단 경로라는 보장이 없음. 3. 스택 오버플로: 재귀 깊이가 너무 깊어지면 Unity 엔진에서 StackOverflowException 발생 가능

 

 

---

핵심 차이점 요약

구분	DFS (깊이 우선)	BFS (너비 우선)
자료구조	스택(Stack) 또는 재귀(Recursion)	큐(Queue)
최단 경로	보장 안 됨	보장됨 (가중치 없는 그래프)
메모리(공간)	경로의 깊이에 비례 (보통 적음)	그래프의 너비에 비례 (많을 수 있음)
추정 방식	경로가 깊을수록 유리 (과소추정 상황)	목표가 가까울수록 유리