DFS(Depth First Search)란?
DFS는 깊이 우선 탐색으로 그래프나 트리에서 한 경로를 따라 최대한 깊이 들어갔다가, 더 이상 갈 곳이 없으면 되돌아오며(backtracking) 다른 경로를 탐색하는 알고리즘이다.
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
List<int>[] adjList = new List<int>[6]
{
new List<int>() { 1, 3 },
new List<int>() { 0, 2, 3 },
new List<int>() { 1 },
new List<int>() { 0, 1, 4 },
new List<int>() { 3, 5 },
new List<int>() { 4 },
};
bool[] visited = new bool[6]; // 방문한 정점 bool 체크
// 인접 행렬 DFS
public void DFS(int now)
{
Console.WriteLine(now);
visited[now] = true;
for (int next = 0; next < 6; next++)
{
if (adj[now, next] == 0) // 연결이 되어있지 않으면
continue;
if (visited[next]) // 이미 방문한 정점이면
continue;
DFS(next); // 연결된 정점 방문(재귀 함수)
}
}
// 인접 리스트 DFS
public void DFS2(int now)
{
Console.WriteLine(now);
visited[now] = true;
foreach (int next in adjList[now])
{
if (visited[next])
continue;
DFS2(next);
}
}
DFS 다음과 같은 순서로 작동한다.
1. 현재 정점을 방문하고
2. 인접한 정점 중 아직 방문하지 않은 정점으로 이동
3. 더 이상 갈 수 없으면 한 단계 돌아감 (Backtracking)
4. 전체 정점을 방문할 때까지 반복한다 (재귀 함수)
위에 그래프(Graph)는 위 인접 행렬과 리스트 행렬을 표현한 예시 그래프 이미지다.
그래프는 정점(Vertex)과 간선(Edge) 이루어진 자료구조로 정점들 사이의 관계를 표현할 때 사용한다.
인접 행렬로 구현된 DFS와 List 행렬로 구현된 DFS 코드들을 실행해서 출력해보면 순서대로 출력이 되는 것을 확인할 수 있다. 처음 방문한 노드를 설정하고 for문과 foreach문을 활용해서 0~6까지의 인덱스 중 간선이 연결된 노드만 순차적으로 방문하기 때문이다.
++ 내부 메소드에서 bool[]을 선언하지 않아도 배열은 이미 참조형이기 때문에 ref 키워드를 인자로 넘겨주지 않아도 값을 정상적으로 할당할 수 있다.
BFS(Breadth First Search)란?
BFS는 그래프에서 시작 정점으로부터 가까운 정점부터 차례대로 탐색하는 알고리즘이다.
BFS에서는 자료구조 중에서 선입선출(First in first out, FIFO)할 수 있는 Queue 자료구조를 활용한다.
DFS와는 달리 특정 노드의 부모 노드를 찾을 수 있고, 특정 정점이 처음 정점으로부터 얼마나 떨어져 있는지도 확인할 수 있다.
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
List<int>[] adjList = new List<int>[6]
{
new List<int>() { 1, 3 },
new List<int>() { 0, 2, 3 },
new List<int>() { 1 },
new List<int>() { 0, 1, 4 },
new List<int>() { 3, 5 },
new List<int>() { 4 },
};
public void BFS(int start)
{
bool[] found = new bool[6];
Queue<int> queue = new Queue<int>();
int[] parent = new int[6]; // 각 정점의 부모 정점
int[] distance = new int[6]; // 각 정점까지의 거리
queue.Enqueue(start);
found[start] = true;
parent[start] = start;
distance[start] = 0;
while (queue.Count > 0)
{
int now = queue.Dequeue();
Console.WriteLine(now);
for (int next = 0; next < 6; next++)
{
if (adj[now, next] == 0) // 인접하지 않으면
continue;
if (found[next]) // 이미 방문한 정점이면
continue;
queue.Enqueue(next);
found[next] = true;
parent[next] = now;
distance[next] = distance[now] + 1;
}
}
}
먼저 BFS의 결과부터 확인해보면 DFS와는 달리 방문한 순서가 다르다는 것을 확인할 수 있다.
BFS는 모든 정점을 가까운 거리부터 탐색하기 때문에, 시작 정점에서부터 한 단계씩 넓게 퍼져 나가듯이 방문하게 된다.
또한, 부모 노드와 처음 정점으로부터의 거리를 parent와 distance로 변수로 받아서 지정해주기 때문에 어떤 정점이 부모 노드였는지, 처음 정점과 얼마나 거리가 먼지 확인할 수 있다.
이 글은 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 참고하여 제작하였습니다.