깊이 우선 탐색(DFS)

🤔 DFS란?

• 그래프 완전 탐색 기법 중 하나이다.
• 스택 자료구조를 이용하여 재귀 함수로 구현이 가능하다.
• 시작 노드에서 출발하여 탐색할 한 쪽 루트를 최대 깊이까지 탐색을 마친 후, 다음 루트로 이동하여 탐색하는 알고리즘이다.
• 시간 복잡도는 O(노드 수 +  에지 수)이다.

👉 DFS 수행 방식

DFS 수행 과정 1

DFS 수행 과정 2

DFS 수행 과정 3

✔️ DFS 과정

1. 스택의 후입선출 특성을 가지고 DFS 탐색 방식을 표현할 수 있다.
2. DFS 시작할 노드를 정하고, 스택 자료구조에 초기화시켜준다. (DFS 수행 과정 1)
3. 방문 리스트에는 스택 자료구조에 추가됨과 동시에 방문 기록을 남긴다.
4. 스택에서 초기화한 노드를 꺼내고, 꺼낸 노드의 이웃 노드를 다시 스택에 추가시켜준다.
5. 마찬가지로 방문 리스트에 방문 기록을 남겨 재방문하지 않도록 설정해준다.
6. 스택 자료구조에 값이 없을 때까지 반복시켜준다.
7. 위와 같은 구조를 반복하여 DFS의 탐색 순서를 살펴본다.