그래프(Graph)는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 다양한 형태의 데이터 간 관계를 표현할 수 있다. 게임에서는 맵의 연결 구조, 캐릭터의 상태 전이(State Machine), 퀘스트 의존성 등에서 그래프 형태의 데이터를 자주 다룬다. 이러한 그래프를 탐색하기 위한 기본적인 알고리즘이 DFS와 BFS이다.
DFS (Depth-First Search, 깊이 우선 탐색)
개념
DFS는 그래프나 트리 구조에서 한 방향으로 가능한 깊은 지점까지 먼저 탐색한 후, 더 이상 진행할 수 없을 때 이전 단계로 되돌아가며 다른 방향을 탐색하는 방식이다. 재귀 호출을 이용하거나, 명시적으로 스택(Stack) 자료구조를 이용하여 구현할 수 있다.
동작 원리
-
현재 노드를 방문 처리한다.
-
인접한 노드 중 방문하지 않은 노드가 있다면, 그 노드를 스택에 넣고 다시 1번으로 돌아간다.
-
더 이상 방문할 노드가 없으면 스택에서 이전 노드로 되돌아간다.
-
모든 노드를 방문할 때까지 위 과정을 반복한다.
활용 예시
-
미로 게임에서 목표 지점까지의 경로를 무작위로 탐색
-
AI가 먼저 도달 가능한 깊은 지역을 순차적으로 탐색할 때
-
재귀 기반의 탐색 구현이 가능한 상황 (단, 스택 오버플로우 주의)
-
랜덤 던전 생성 시, DFS를 통해 복잡한 미로 구조를 생성 가능.
-
플레이어의 선택 경로를 깊이 우선으로 처리하여 특정 조건 충족 시 다음 스킬을 개방하는 구조 구현.
-
추적 행동에서 일시적으로 가장 깊은 경로를 탐색하도록 설정 가능.
void DFS(Dictionary<int, List<int>> graph, int node, HashSet<int> visited)
{
if (visited.Contains(node)) return;
visited.Add(node);
Debug.Log("Visited: " + node);
foreach (int neighbor in graph[node])
{
DFS(graph, neighbor, visited);
}
}
BFS (Breadth-First Search, 너비 우선 탐색)
개념
BFS는 DFS와는 반대로, 가까운 노드부터 차례로 탐색해 나가는 방식이다. 탐색 대상은 큐(Queue) 자료구조를 이용하여 관리되며, 가장 가까운 거리에 있는 노드부터 순차적으로 탐색하게 된다.
동작 원리
-
시작 노드를 큐에 넣고 방문 처리한다.
-
큐에서 노드를 꺼낸다.
-
해당 노드의 인접한 노드 중 방문하지 않은 노드를 큐에 추가하고 방문 처리한다.
-
큐가 빌 때까지 위 과정을 반복한다.
활용 예시
-
NPC 경로 탐색: 최단 거리 계산 시 BFS는 가장 기본적이고 정확한 선택이다.
-
퍼즐 게임 구현: 상태 공간을 너비 우선으로 탐색하여 정답 도출 시 활용.
-
네비게이션 메시 없이 간단한 길찾기: 타일 기반 이동 구조에서 장애물 회피 등 간단한 로직 처리에 적합.
void BFS(Dictionary<int, List<int>> graph, int start)
{
Queue<int> queue = new Queue<int>();
HashSet<int> visited = new HashSet<int>();
queue.Enqueue(start);
visited.Add(start);
while (queue.Count > 0)
{
int node = queue.Dequeue();
Debug.Log("Visited: " + node);
foreach (int neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}DFS vs BFS 비교
| 항목 | DFS | BFS |
|---|---|---|
| 자료 구조 | 스택 (Stack) 또는 재귀 | 큐 (Queue) |
| 사용 목적 | 완전 탐색, 깊은 조건 탐색 | 최단 경로 탐색 |
| 공간 복잡도 | 상대적으로 낮을 수 있음 (경우에 따라) | 노드가 많을 경우 큐 크기가 커짐 |
| 구현 난이도 | 재귀적 구조로 간결 | 반복문과 큐로 구현 |
| 예시 활용 | 미로 생성, 스킬 트리, 백트래킹 문제 | 최단거리 탐색, 전염병 시뮬레이션 등 |
마무리
DFS와 BFS는 단순한 알고리즘 같지만, 게임 시스템 설계와 구현에서 전략적으로 매우 유용하게 활용될 수 있다. Unity 프로젝트를 설계할 때, 단순한 길찾기부터 스테이트 기반 AI, 스킬 전개, 맵 탐색 등에서 이들 탐색 알고리즘을 적절히 조합하면 더욱 정교한 시스템을 구축할 수 있다.
