깊이우선탐색(DFS)

깊이우선탐색(Depth-First Search)

DFS는 그래프 완전 탐색 기법 중 하나로,
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

그래프 탐색이란 ?
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 기법이다.

---

깊이우선탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘 형태이다.
  재귀 함수를 이용하므로 스택 오버플로우(stack overflow) 유의
• 그래프 탐색의 경우 노드의 방문 여부 검사가 필요하다.
  방문 여부를 검사하지 않을 경우 무한루프 유의
• 시간복잡도( V : 노드 수 / E : 에지 수 )
  인접 리스트를 이용하여 구현하는 경우 : O(V+E)
  인접 행렬을 이용하여 구현하는 경우 : O(N^2)

깊이우선탐색(DFS)의 탐색과정

1. 현재 노드를 방문한 것으로 표시한다.
2. 방문 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3. 더 이상 방문하지 않는 정점이 없으면 이전 정점으로 백트래킹한다.
4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

깊이우선탐색(DFS)의 구현방법

• 반복문(스택 자료구조 사용)
• 재귀함수