깊이 우선 탐색(DFS)

• Root node에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때, 정해진 방향으로 끝까지 가보고 더 이상 갈 수 없을 때 다시 가장 가까운 갈림길로 돌아와 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사

• 다시말하면, 시작 정점에서 부터 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식

• 즉, 넓게 탐색하기 전에 깊게 탐색하는 방식

---

특징

• 자기 자신을 호출하는 순환 알고리즘 형태

• 그래프 탐색의 경우 어떤 노드를 방문했는지 반드시 검사를 해여 하며, 미검사시 무한 루프에 빠질 위험이 있다.

---

장단점

장점

• 모든 노드를 방문하고자 하는 경우에 사용

• 단지 현 경로상의노드들만 기억하면 되므로 저장 공간의 수요가 적다.

• 목표 노드가 깊은 단계에서 있을 경우 답을 빨리 구할 수 있다.

• 깊이 우선 탐색(DFS)가 너비 우선 탐색(BFS)보다 더 간단하다.

단점

• 단순 검색 속도의 경우 너비 우선 탐색(BFS)보다 느리다.

• 얻어진 답이 최단 경로가 된다는 보장이 없다.

• 목표에 이르는 경로가 여러개인 경우, 하나의 답에 다다르면 탐색을 종료해버리므로 이때 답이 최적이 아닐 수 있다.

---

DFS 과정

1. 0번 정점 방문

2. 0번 정점과 인접한 정점 중 가장 값이 작은 1번 정점 방문

3. 1번 정점과 인접하고, 아직 방문하지 않은 정점 중 가장 작은 2번 정점 방문

4. 2번 정점과 인접하고, 아직 방문하지 않은 정점 중 가장 작은 3번 정점 방문

5. 3번 정점과 인접하고, 아직 방문하지 않은 정점 중 가장 작은 4번 정점 방문

6. 4번 정점과 인접하고, 아직 방문하지 않은 정점 중 가장 작은 5번 정점 방문

7. 6번 정점과 인접하고, 아직 방문하지 않은 정점 중 가장 작은 5번 정점 방문 후 더 이상 방문하지 않은 정점이 존재하지 않으므로 종료

• 최종 순서의 경우 0 → 1 → 2 → 3 → 4 → 6 → 5 순서

---

Code