깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 한다.
깊이 우선 탐색은 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
깊이 우선 탐색의 핵심 이론
DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
DFS 구현은 재귀 함수로 많이 구현합니다.
그래프는 보통 인접행렬, 인접리스트(많이 사용)로 표현 가능하다.
- DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다. 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F가 된다.
- 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽힙하며 방문 배열을 체크한다. 방문 배열은 T,T,T,F,F,F가 된다.
- 스택 자료구조에 값이 없을 때까지 반복하기
앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심
