깊이 우선 탐색(DFS)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
DFS의 주요 특징
-
동작 방식: 루트 노드(또는 다른 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
-
탐색 방식: 후입선출 특성을 가지므로 스택을 사용(재귀 함수 호출 시 새로운 스택 프레임 생성하기 때문에 스택 성질을 가짐)하며, DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
-
구현 방법: 주로 재귀 함수나 스택을 사용하여 구현
-
활용: 경로의 특징을 저장해야 하는 문제나 목표 노드가 깊은 단계에 있는 경우에 효과적
깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.
DFS의 동작 방식
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다. 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T, F, F, F, F, F가 된다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
이제 pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다. 방문 배열은 T, T, T, F, F, F가 된다.
3. 스택 자료구조에 값이 없을 때까지 반복하기
앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
시간 복잡도
-
인접 행렬 사용 시: O(V^2) (V는 노드의 개수)
-
인접 리스트 사용 시: O(V+E) (E는 간선의 개수)
장단점
장점:
-
현재 경로상의 노드들만 기억하므로 저장 공간이 적게 든다.
-
목표 노드가 깊은 단계에 있을 경우 해를 빨리 찾을 수 있다.
단점:
-
해가 없는 경로에 깊이 빠질 가능성이 있다.
-
얻어진 해가 최단 경로라는 보장이 없다.
