DFS(Depth First Search) 깊이 우선 탐색
깊이 우선 탐색(DFS)
- 그래프 탐색의 방법중 하나 (그래프 탐색 : 하나의 노드로부터 나머지 모든 노드까지 차례대로 탐색하는 것)
동작 원리
- 하나의 노드로부터 자식 노드를 확인할 때, 모든 자식노드를 먼저 탐색하지 않고 한 자식노드에 대한 자식노드를 우선시 한다.
예)
1. 0번 노드부터 시작할 때, 자식노드 1과 2중 먼저 들어온 1을 확인한다.
2. 노드 1을 탐색하고 노드 1에 대한 자식노드 3, 4중에 먼저 들어온 3을 탐색한다.
3. 노드 3을 탐색하고 노드 3에 대한 자식노드가 없으므로 노드 3의 부모노드인 노드 1로 재귀(back-tracking)한다.
4. 노드 1의 자식노드 중 노드 3은 이미 탐색 했으므로 탐색하지 않은 노드 4를 확인한다.
5. 노드 4에 대한 자식노드가 없으므로 노드 4의 부모노드인 노드 1로 재귀한다.
6. 노드 1의 모든 자식 노드를 탐색했으므로 노드 1의 부모 노드인 노드 0으로 재귀한다.
7. 노드 0의 자식노드 1, 2중 1은 이미 탐색했으므로 노드 2를 확인한다.
8. 노드 2를 탐색하고 노드 2의 자식노드 5, 6중에 먼저 들어온 노드 5를 탐색한다.
9. 노드 5를 탐색하고 노드 5에 대한 자식노드가 없으므로 부모노드인 노드 2로 재귀한다.
10. 노드 2의 자식노드 5, 6중 5는 이미 탐색했으므로 노드 6을 탐색한다.
11. 노드 6을 탐색하고 노드 6은 자식노드가 없으므로 부모노드로 회귀한다.
12. 모든 노드에 대한 탐색이 끝났으므로 종료한다.
주의요소
- DFS를 구현할때는 노드에 대한 방문 여부를 꼭 체크해야 한다.
-> 체크하지 않으면 무한 루프에 빠지기 쉽다.
시간복잡도(Big O)
- DFS는 모든 노드를 탐색하므로
노드의 수 : N, 간선의 수 : E 일 때
인접리스트 그래프 : O(N+E)
인접행렬 그래프 : O(N^2) 의 시간복잡도를 가진다.