• 그래프 완전 탐색 기법 중 하나
• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

• 스택 자료구조 이용 | O(V + E) |

• 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의
• 응용문제
  • 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등

핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 설명
  • DFS 구현은 스택보다는 재귀 함수로 많이 구현

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

3. 스택 자료구조에 값이 없을 때까지 반복

• 스택에 노드를 삽입할 때 방문 배열을 체크