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

이번 포스팅은 그래프를 탐색하는 알고리즘 중 하나인 깊이 우선 탐색(DFS)에 대해 알아보려고 한다.

 

[자료구조] 그래프 (Graph)

 

현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

---

📝 개념

처음 시작할 때 그래프의 구조를 모르는 상태에서, 어떤 정점(시작점)에 위치 하고 있다고 가정해보자.

목적은 간선에 따라가며 지정된 정점(목표)에 도달하는 것이다.

지정된 정점에 도착하면 해당 정점이 목표인지 여부를 판단하는데, 깊이 우선 탐색은 하나의 길을 선택하여 갈 수 있는 만큼 진행하다가 더 이상 진행할 수 없으면 되돌아가서 다음 후보 경로를 탐색한다.

 

깊이 우선 탐색

현재 위치를 빨간색 테두리로 표시해 두었다.

A를 시작점, G를 목표라고 해두었다.

 

깊이 우선 탐색

A에서 도달할 수 있는 정점 B, C, D가 다음 진행할 정점 후보가 된다.

후보가 되는 정점은 연두색으로 표시해 두겠다.

 

깊이 우선 탐색

후보 중에서 정점을 하나 선택한다. 선택 기준은 후보 중에서 최근에 후보에 추가된 것이다. 같은 시점에 후보가 된 정점 중에서는 어떤 것을 선택해도 무방하다. 여기서는 왼쪽에 있는 정점부터 선택하겠다.

 

깊이 우선 탐색

B, C, D가 같은 시점에 후보가 되었기 때문에 가장 왼쪽에 있는 B를 다음 정점으로 선택하겠다.

선택된 정점은 주황색으로 표시하겠다.

 

깊이 우선 탐색

선택한 정점 B로 이동한다. 현재 위치인 B를 빨간색으로 표시한다. 탐색이 끝난 정점은 주황색으로 표시한다.

 

깊이 우선 탐색

현재 위치인 B에서 이동할 수 있는 E와 F를 새로운 후보로 추가한다.

 

깊이 우선 탐색

후보 [D, C, F, E]에서 최근에 추가된 정점은 E와 F다. 그중 왼쪽에 있는 E를 선택한다.

 

깊이 우선 탐색

선택한 정점으로 이동한다.

 

깊이 우선 탐색

현재 위치인 E에서 이동할 수 있는 K를 새로운 후보로 추가한다.

 

깊이 우선 탐색

목표에 도달하거나 모든 정점에 대한 탐색이 완료될 때까지 같은 작업을 반복한다.

 

깊이 우선 탐색

이 예에서는 [A, B, E, K, F, C, H]순으로 선택된다.

 

깊이 우선 탐색

현재 C까지 탐색한 상태다.

 

깊이 우선 탐색

목표인 G에 도착했기 때문에 탐색을 종료한다.

 

이처럼 깊이 우선 탐색은 한 경로를 깊이 있게 파 내려가면서 탐색을 진행하는 특징이 있다.

 

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)의 탐색 순서는 많이 다르지만, 절차상 차이점은 후보 정점 중에서 다음 정점을 선택하는 방법이다.

너비 우선 탐색은 가장 먼저 후보가 된 정점을 선택하며, 시작점에서 가까운 정점이 먼저 후보가 되기 때문에 시작점에서 가까운 순서로 탐색한다. 반면, 깊이 우선 탐색은 최근에 후보가 된 정점을 선택하므로 새롭게 발견한 길을 계속 파고들면서 탐색한다.

---

✔️추가 내용

깊이 우선 탐색을 실시 할 때 후보의 정점은 '후입선출(LIFO)' 구조로 관리하므로 스택(Stack) 데이터 구조를 사용한다.

[자료구조] 스택 (Stack)

 

깊이 우선 탐색(DFS) 장점

• 한 경로상의 정점만 기억하면 되기 때문에 저장공간의 수요가 적다
• 목표 정점이 깊은 단계에 있을 경우 목표를 빨리 찾을 수 있다.

 

깊이 우선 탐색(DFS) 단점

• 목표가 없는 경로에 깊이 빠질 수 있다.
• 얻은 목표가 최단 경로가 된다는 보장이 없다.

 

깊이 우선 탐색은 특정 시나리오에서는 유용할 수 있지만, 항상 최선의 선택은 아니다. 해결하려는 문제에 따라 너비 우선탐색이 더 적합할 수 있다.

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

 

깊이 우선 탐색 : 위키 백과

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란? : olrlobt

https://olrlobt.tistory.com/35