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

</aside>

깊이 우선 탐색은 실제 구현 시 재귀 함수를 사용하므로 스택 오버플로우에 유의해야 한다.

깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

깊이 우선 탐색 과정

1. 시작 노드를 스택에 저장
2. 맨 앞의 값을 꺼냄
3. 꺼낸 값으로 문제에서 요구하는 연산을 수행
4. 인접 노드를 스택에 저장
5. 스택이 빌 때까지 2~5까지의 과정을 반복

깊이 우선 탐색의 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 여기서 그래프는 인접 리스트로 표현한다. (인접 행렬로도 가능한데 인접 리스트를 많이 사용한다고 함)

<aside> 💡 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 ****노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.

</aside>

DFS의 용도

1. 그래프 순회
2. 백트래킹
3. 미로 찾기