DFS(깊이 우선 탐색)

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

노드 개수를 V, 엣지 개수를 E로 표시

• 스택 자료구조는 First-in Last-out의 구조이며 재귀함수와 구조가 같음
• 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 한다.
• 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

깊이 우선 탐색의 핵심 이론

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

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

• DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기
• 스택에 시작 노드를 1로 삽입할 때, 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F가 된다.

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

• 이제 pop을 수행하여 노드를 꺼낸다.
• 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다.
• 방문 배열은 T,T,T,F,F,F가 된다.

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

• 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다.
• 핵심은 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것

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

---

출처 - 하루코딩