Search Algorithm [1]. 깊이 우선 탐색 (Depth First Search : DFS)

깊이 우선 탐색 (Depth First Search : DFS)

깊이 우선 탐색 이란?

* 사전적 정의 : 깊이 우선 탐색은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해가는 방식이다.

* 간단한 정의 : 원하는 해를 찾기 위해서 전진할 수 있을 때 까지 전진하고, 만약 전진하다가 나아갈 길이 보이지 않는다면 바로 전에 선택한 갈림길에서 다른길을 선택하여 또 전진하는 방식이다.

깊이 우선 탐색은 말 그대로 깊이를 우선적으로 하여 탐색하는 방법을 말한다. 비슷한 탐색 방법으로는 너비 우선 탐색(Breadth First Search : BFS) 가 있는데 이것 역시 말 그래로 너비를 우선적으로 하여 탐색을 하는 방법을 말한다.

<그림 1>

데이터가 <그림 1> 같은 트리 구조로 되어 있다고 가정을 해보자. 

<그림 2>

이때 깊이 우선 탐색은 <그림 2>와 같은 방식으로 노드를 탐색한다. 

<그림 2>와 같은 방식을 <그림 1>에 적용시켜 본다면 

[A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G-> N -> O] 

의 순서로 노드들을 탐색할 것이다.

깊이 우선 탐색 의 데이터 저장 구조

깊이 우선 탐색은 1개의 노드에서 자식 노드를 첨가하고 첨가한 자식 노드에서 또 자식 노드를 첨가하는 식으로 데이터를 확장한다.

이때 나중에 들어온 자식노드에서 새로운 확장을 해 나가기 때문에 Last In First Out(LIFO) 의 구조를 발견할 수 있다.

데이터 저장구조에서 Last In First Out(LIFO)에 가장 적합한 것은 Stack 구조이다.

따라서 깊이 우선탐색을 사용할 때에는 Stack을 저장구조로 사용하는 것이 매우 편리하다.

깊이 우선 탐색 의 탐색 과정 & 데이터 저장 과정

* 아래의 그래프 쉽게 보는 법

- 초록색 점선으로 이루어진 노드는 아직 방문한적도 없고 스택에 들어있지도 않은 노드를 의미

- 실선에 흰색 배경인 노드는 현재 스택에 들어있는 노드를 의미

- 실선에 회색 배경인 노드는 방문한 적이 있는 노드를 의미

- 검은색으로 칠해진 노드는 방문한 적이 있고 그 노드 아래의 자식 노드들까지 전부 방문했음을 의미

(1)	Stack = [A]
(2)	Stack = [B, C]
(3)	Stack = [D, E, C]
(4)	Stack = [H, I, E, C]
(5)	Stack = [I, E, C]
(6)	Stack = [E, C]
(7)	Stack = [J, K, C]
(8)	Stack = [K, C]
(9)	Stack = [C]
(10)	Stack = [F, G]
(11)	Stack = [L, M, G]
(12)	Stack = [M, G]
(13)	Stack = [G]
(14)	Stack = [N, O]
(15)	Stack = [O]

깊이 우선 탐색 의 속성

(d는 데이터 트리 전체 깊이를 의미하고, b는 자식 노드의 개수를 의미한다.)

* 시간 복잡도 (Time Complexity)

트리의 깊이가 목적 노드 깊이와 같을 때 최악의 경우 모든 노드를 다 검사하게 되는데 이때 전체 시간은 아래와 같다.

따라서 깊이 우선 탐색의 시간 복잡도는   이다.

* 공간 복잡도 (Space Complexity)

저장 공간에 저장해야할 노드들은 트리에서 루트 노드로부터 어떠한 노드까지의 경로상에 있는 각 노드의 자식들 중 해당 노드를 제외한 것들이다.

이때 가장 긴 경로의 길이가 d 이므로 최악의 경우 깊이 우선 탐색에서 사용하는 전체 저장 공간은 아래와 같다.

따라서 깊이 우선 탐색의 공간 복잡도는  이다.

깊이 우선 탐색 의 장단점

* 장점

- 현재 탐색하고 있는 경로상의 노드들만을 기억하면 되기때문에 공간 복잡도가 비교적 작다.

- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

* 단점

- 해가 속해 있지 않은 깊은 경로에 빠질 가능성이 있다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다. 목표에 이르기 까지의 경로가 여러개인 경우 최적의 해가 아닐 가능성이 있다.

깊이 우선 탐색 의 의사코드(수도코드, Pseudo Code)

DFS(G,v)   ( v is the vertex where the search starts )

    Stack S := {};   ( start with an empty stack )

    for each vertex u, set visited[u] := false;

    push S, v;

    while (S is not empty) do

        u := pop S;

        if (not visited[u]) then

            visited[u] := true;

            for each unvisited neighbour w of u

                push S, w;

        end if

    end while

      END DFS()