DFS 알고리즘 (깊이 우선 탐색)

DFS(Depth-First Search), 깊이 우선 탐색이란 전 탐색(Full-Search)의 한 종류로 더 이상 이동이 가능하지 않을 때까지 진행하다가 이동이 불가능하면 다시 전 단계로 돌아와 가능한 길을 찾아 움직이는 탐색 방법이다.다른 종류로는 BFS

(Breadth-First search)너비 우선 탐색이 있다.각종 프로그래밍 대회나 정보올림피아드에서 자주 나오는 문제 유형이므로 확실히 이해해두면 분명 도움이 될만한 알고리즘이다.

1. 1에서 2로 이동한다.

2. 2에서 3으로 이동한다.

3. 3에서 4로 이동한다.

4. 4에서 3으로 되돌아온다.(4에서는 더 진행할 곳이 없기 때문이다.)

5. 3에서 5로 이동한다.

6. 5에서 3으로 되돌아온다.(5에서도 더 진행할 곳이 없기 때문이다.)

7. 3에서 2로 되돌아온다.(3에서 진행가능한 곳은 모두 탐색했기 때문이다.)

8. 2에서 6으로 이동한다.

9. 6에서 2로 되돌아온다.(6에서도 마찬가지로 더 진행할 곳이 없기 때문이다.)

10. 2에서 1로 이동한다.

11. 1에서 7로 이동한다.(반복한다.)

 

결국 이 그래프에서의 이동은 적혀있는 순서대로 움직이게된다.

이런 방식으로 모든 수를 찾아 해답을 구하는 것이다.

 

DFS는 스택(stack)를 이용하고 BFS는 큐(Queue)를 이용한다. 그리고 DFS에서 스택을 쓸 수 있다고 할 수 있지만, 이는 원론적인 개념에 대한 이야기이고, 코딩테스트에서는 보통 재귀를 쓴다. 우선 비선형 구조에 대해 간단히 알아보고 DFS를 마스터 하는게 더 나을것이다.