📍 DFS란?
: Depth-First Search(깊이우선탐색)으로,
루트 노드(혹은 다른 임의의 노드)에서 시작해서 가능한 한 깊게 탐색한 후 더 이상 탐색할 수 없을 경우 이전 노드로 되돌아가서 다음 경로를 탐색한다.
-> 모든 노드를 탐색할 때 사용한다.
1. BFS vs DFS
(1) 깊이 우선 탐색 DFS
- 노드 간의 "하나 하나" 모든 관계를 알아야 할 때 사용한다.
- 재귀적인 특성을 가진다. -> 재귀함수 사용
- 후입선출(LIFO) 원칙으로 탐색 -> 스택 사용
(2) 너비 우선 탐색 BFS
- 노드의 최단 경로를 찾을 때 사용한다.
- 깊이 관련 특성을 가진다.
- 재귀적인 특성을 가지고 있지 않다.
- 선입선출(FIFO) 원칙으로 탐색 -> 큐 사용
2. DFS 해결 방식
스택 또는 재귀를 이용하여 해결한다.
(1) 스택
스택에 가장 깊은 노드까지 삽입한다.
스택 pop한 후 그 노드에 연결된 가장 깊은 노드까지 삽입한다.
스택이 empty할 때까지 위의 과정을 반복한다.
(2) 재귀
출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
3. 시간복잡도
- DFS의 시간 복잡도 : O(V + E)
노드 수(V): 그래프에 있는 노드(정점)의 수
간선 수(E): 그래프에 있는 간선(엣지)의 수
