DFS (Depth First Search) 알고리즘

DFS란 ?

Depth First Search라는 의미로, 깊이 우선 탐색이라고도 한다.

하나의 노드에서 시작하여 마지막 지점까지 계속 탐색하는 행동을 하는 알고리즘인데

즉, 시작점을 기준으로 가장 아래까지 이동하면서 탐색하는 방식이다.

이 탐색 알고리즘은 스택을 이용하여 푸는 방식으로, 

스택에 값을 넣어주고. 그 값을 통해 확인하며 종료 조건은 스택이 비어있을 때이다.

DFS는 그림을 참조해서 확인하면 좀더 쉽게 알 수 있다. 

이 DFS의 장점으로는 깊은 곳에 있을수록 빨리 찾아낼 수 있지만,

단점으로는 자칫하면 overflow가 날 수 도있고, 그렇게 얻어진 해가 최단 거리라는 보장은 없다.

DFS 탐색 알고리즘 코드는 http://www.crocus.co.kr/519 이 링크에서 확인해 볼 수 있다.

 우선 이렇게 구성되어 있는 그래프가 있다 하자.

(DFS는 꼭 그래프에서 이용하는 탐색 알고리즘은 아니지만, 편의상 그래프로 설명하도록 한다.)

 

 1번 노드(혹은 정점)부터 시작하도록 하며, 스택에 1을 넣어준다.

다음으로는 1 다음으로 갈 수 있는 노드를 확인한다.

2가 이에 해당하며, 2를 스택에 쌓으며(push) 2를 방문해준다.

이후, 2 다음으로 방문할 곳이 없으니 2를 스택에서 빼고 1에서 다른곳을 방문할 수 있는곳이 있는지 확인한다.

3을 방문할 수 있으니 3을 방문하고, 스택에는 3을 쌓아준다.

3다음에는 5를 방문하며 스택에 쌓아주고,

5 다음에 방문할 곳이 없으니 스택에서 뺀다. 다시 3에서 방문할 수 있는곳을 확인한다.

(스택의 가장 위의 값으로 확인하고 있는것을 알고있어야 한다.)

6을 방문하고 계속해서 반복한다.

이렇게 10까지 모두 방문한 뒤, 스택에는 현재 10이 가장 위에있다.

10다음에 방문할 곳이 없으니 10을 빼고, 9, 7, 6, 3 모두 다 방문한 상태이니 스택에서 자연스레 빠질것이다.

1에 왔을 때, 1은 4에 아직 방문할 수 있다.

4를 방문하고 스택에 쌓아준 후, 4가 방문할 곳이 없으니 스택에서 빼고 1도 마찬가지로 뺀다.

이렇게 스택이 텅 비게 되면 이 탐색 알고리즘은 끝이나게된다.

방문 순서는 결과적으로

1->2->3->5->6->7->8->9->10->4 순서이다.