DFS(깊이 우선 탐색)란?
- DFS는 그래프 완전 탐색 기법 중 하나
- 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
기능 : 그래프 완전 탐색
특징 : 재귀 함수로 구현, 스택 자료구조 이용
시간 복잡도(노드 수 : V, 에지 수 : E) : O(V + E)
- DFS는실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야함
DFS의 핵심 이론
- 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
- 탐색 방식은 후입선출 특성을 가짐(실제로는 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현)
방식
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현, 방문 배열 초기화, 시작 노드 스택에 삽입
- 예시) 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입
- pop을 수행하여 노드를 꺼내고, 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크
- 예시) 방문 배열은 T,T,T,F,F,F
3. 스택 자료구조에 값이 없을 때까지 반복
- 앞의 과정을 스택 자료구조에 값이 없을 때까지 반복
- 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심
study