DFS
#
Find similar titles
- 최초 작성자
- 최근 업데이트
Structured data
- Category
- Algorithm
DFS (Depth First Search) #
DFS (Depth First Search, 깊이우선탐색)는 BFS (Breath First Search, 너비우선탐색) 와 더불어 Tree를 조사하는 가장 기본적인 알고리즘 중 하나로 Root Node를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법(자식우선탐색)이다. 이렇듯 깊이를 우선적으로 탐색하기 때문에 그래프의 최대 경로가 정해져 있거나, 깊이를 예측할 수 있는 경우에 주로 사용된다.
더 이상 방문할 정점이 없을 때 최근 분기점으로 돌아오는 로직은 Stack 또는 재귀함수(Recursive Function)를 이용해 구현한다. 이와 달리 BSF는 Queue를 이용하여 구현한다.
DFS 알고리즘 #
Stack을 이용한 DFS 알고리즘
- 시작 정점(Root Node)를 push
- Stack에서 노드 하나를 pop
- Stack에서 꺼낸 노드가 아직 방문하지 않은 노드라면 방문 표시 후 인접 노드를 push
- Stack에 남은 노드가 없을 때까지 2,3 단계를 반복
Recursive Function을 이용한 DFS 알고리즘
- Parameter로 넘어온 노드가 이미 방문한 노드인경우 return 하도록 stop condition 설정
- Parameter로 넘어온 노드가 방문하지 않은 노드인 경우 방문 표시
- 인접 노드에 대해 재귀적으로 함수를 호출하며 탐색 진행
DFS의 장·단점 #
DFS 장점 #
- 현 경로상의 노드만 기억하면 되므로 공간 복잡도의 비용 저하
- 목표 노드가 깊은 단계에 있을 경우 비교적 빠른 시간내에 탐색 가능
DFS 단점 #
- 목표 노드가 없는 경로가 깊은 depth인 경우 탐색이 오래 걸릴 수 있음
- 얻어진 목표 노드까지의 경로가 최단 경로라는 보장이 없음
DFS 시간복잡도 #
DFS는 그래프의 모든 간선을 조회한다. 그래프의 구성요소를 노드(N)와 간선(E)으로 표현했을 때 구현 방법에 따른 시간복잡도는 다음과 같다.
- 인접리스트 : 모든 노드를 탐색하는 최악의 경우를 제외한 나머지 경우 인접행렬보다 빠른 시간복잡도 O(N+E)
- 인접행렬 : 노드의 수가 적은 경우에 사용하는 것을 추천. N개의 노드에 대해 행렬의 크기가 N*N만큼 차지하기에 시간복잡도는 O(N^2)