깊이우선 탐색 DFS

깊이 우선 탐색, Depth_-First-Search(이하 DFS)은 그래프를 탐색하는 대표적인 알고리즘이다.

 

이름에서 유추할 수 있듯, 하나의 지점에서 가장 깊은 깊이까지 파고들며 탐색을 진행한다.

 

먼저 그래프는 정점과 간선으로 이루어져 있다. 정점은 노드라고도 부르며 간선은 각 정점을 잇는 선이다.

아래의 그림에서 원 하나를 정점이라고 하고, 정점을 잇는 선이 간선이다.

 

DFS의 주요한 특징은 바로 스택 자료구조를 이용한다는 것이다.

DFS를 할 때에는 재귀함수를 주로 이용하게 된다. 왜냐하면, 함수를 호출하게 되면 호출된 함수는 종료되기 전까지 스택 메모리 구조에 남아있게 된다.

따라서 BFS와 달리 Queue나 Dequeue를 따로 만들어 주지 않아도 자동적으로 스택을 이용해서 데이터를 탐색하는 것이 된다. 이 때문에 다른 대표적인 탐색 알고리즘인 BFS와 달리 스택을 이용한다는 것이 코드로 눈에 확 보이지는 않는 것 같다.

 

탐색을 시작해보자.

현재 탐색하는 노드는 빨간색으로, 이미 방문한 노드는 주황색으로 표시한다.

그리고 스택 공간에 쌓이는 노드들은 '해당 노드를 탐색하기 위해 호출된 함수'가 쌓이는 것으로 이해해도 무방하다.

1번 노드부터 탐색을 시작한다. 1번이 아닌 다른 노드부터 탐색을 시작할 수도 있지만, 숫자가 낮은 노드부터 오름차순으로 진행하는 것이 이해에 도움이 되고, 실제 코딩시에도 편하다.

 

그리고 해당 노드를 방문했다는 것을 저장하기 위해 따로 리스트 혹은 배열을 이용해 체크해준다. (실제 코딩할 때에는 boolean을 이용해 True, False로 표시한다.)

 

첫 번재 노드를 탐색했다. 1번 노드가 스택 공간에 쌓이고 방문 여부 리스트의 1번에 방문했다는 표시를 해주었다.

이제 1번 노드의 인접 노드인 2번과 3번 노드 중에 먼저 탐색할 노드를 정해야 하는데, 통상 숫자가 작은 노드를 먼저 탐색해준다.

노드를 숫자가 아닌 문자나 변수로 지정하고 탐색을 해야 하는 경우도 발생하는데, 이 때에는 나름의 기준을 정해 프로그램이 동작하게 만들어주면 된다.

 

2번 정점을 탐색하고 스택공간에 2번 정점을 쌓아준다. 마찬가지로 방문 여부 리스트의 2번에 표시를 해준다.

 

2번의 인접 노드인 1번과 7번 노드 중 이미 탐색한 1번 노드를 제외하고 7번 노드를 탐색한다. 여기서 1번 노드의 탐색을 스킵하기 위해 방문 여부 리스트를 사용한다는 것을 이해할 수 있다. 스택 공간에도 7번 노드를 쌓아준다.

 

7번 노드의 인접 노드인 8번과 6번 노드 중 숫자가 작은 6번 노드부터 탐색한다. 스택 공간에 마찬가지로 6번 노드가 쌓이고 방문 여부 리스트에도 표시를 해준다.

 

6번 노드의 인접 노드에는 더이상 방문하지 않은 노드가 존재하지 않는다. 그렇다면 6번 노드를 스택에서 꺼내주고(함수 종료), 다시 7번 노드의 인접 노드 중 방문하지 않은 8번 노드를 방문하고 스택을 쌓아준다. 마찬가지로 방문 여부 리스트에도 계속해서 표시를 해준다.

 

이제 8번 노드의 인접 노드(1번, 7번) 중에서도 더이상 방문하지 않은 노드가 없다.

6번 노드에서 7번 노드로 넘어갈 때 처럼 방문하지 않은 인접노드가 없어 8번을 꺼내고 7번 노드에서 검사한다.

7번 노드의 인접 노드에서도 방문하지 않은 노드가 없으므로 2번 노드로 넘어가 미방문 노드를 검사한다.

마찬가지로 2번 노드에서도 방문하지 않은 노드가 없으므로 스택에서 꺼내주고 1번 노드로 넘어가 검사한다.

 

1번 노드의 인접노드 중에서는 방문하지 않은 3번 노드가 있었다. 3번 노드를 방문하고 스택에 쌓은 뒤 방문 여부 리스트에 표시를 해준다.

 

이제 위와 같은 과정을 반복하면 된다.

 

이제 모든 노드를 검사했다. 마찬가지로 5번 노드부터 다시 거슬러 미방문 노드를 탐색해준다.

 

루트 노드인 1번 노드까지 거슬러 검사해도 방문하지 않은 노드가 없으므로 탐색이 종료되고 스택 또한 비워진다.

 

DFS 알고리즘의 동작 모습을 보면, 하나의 노드에서 '도달할 수 있는 가장 먼 노드까지 탐색' 한다는 특징이 있다.

또한 실제 코딩 시 반복문을 이용할 수 있는데 주로 재귀함수를 이용하게 된다.