[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)

깊이 우선 탐색(DFS)이란?

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

깊이 우선 탐색(DFS) 특징

• Stack을 이용합니다.
• 자기 자신을 호출하는 순환 알고리즘의 형태이므로 재귀함수를 사용합니다.
• 탐색 과정에서 어떤 값을 탐색하였는지 여부를 반드시 검사해야 합니다.

깊이 우선 탐색(DFS) 동작 예시

1. A를 시작 지점이라 하고 A를 꺼내 스택(Stack) 저장소에 저장 합니다.

2. A를 스택(Stack) 저장소에서 꺼낸 후 A와 인접한 B, D를 스택(Stack) 저장소에 저장합니다.

3. D를 스택(Stack) 저장소에서 꺼낸 후 D와 인접한 A,E가 있지만 A는 이전에 탐색한 적이 있으므로 E만 스택(Stack) 저장소에 저장합니다.

4. E를 스택(Stack) 저장소에서 꺼낸 후 E와 인접한 C,D가 있지만 D는 이전에 탐색한 적이 있으므로 D만 스택(Stack) 저장소에 저장합니다.

5. C를 스택(Stack) 저장소에서 꺼낸 후 C와 인접한 B,E,F가 있지만 B,E는 이전에 탐색한 적이 있으므로 F만 스택(Stack) 저장소에 저장합니다.

6. F를 스택(Stack) 저장소에서 꺼낸 후 F와 인접한 C,G,H가 있지만 C는 이전에 탐색한 적이 있으므로 G,H만 스택(Stack) 저장소에 저장합니다.

7. H를 스택(Stack) 저장소에서 꺼낸 후 H와 인접한 F,I가 있지만 F는 이전에 탐색한 적이 있으므로 I만 스택(Stack) 저장소에 저장합니다.

8. I를 스택(Stack) 저장소에서 꺼낸 후 I와 인접한 H가 있지만 이전에 탐색한 적이 있으므로 스택(Stack) 저장소에는 저장되는 값이 없습니다.

9. G를 스택(Stack) 저장소에서 꺼낸 후 G와 인접한 F가 있지만 이전에 탐색한 적이 있으므로 스택(Stack) 저장소에는 저장되는 값이 없습니다.

10 . B를 스택(Stack) 저장소에서 꺼낸 후 B와 인접한 A,C가 있지만 이전에 탐색한 적이 있으므로 스택(Stack) 저장소에는 저장되는 값이 없습니다. 이 후 스택(Stack) 저장소에는 저장된 값이 없으므로 모든 탐색이 종료됩니다.