🚀 What I Will Learn

• 깊이 우선 탐색(Depth First Search, DFS)에 대해 이해하기

깊이 우선 탐색(Depth First Search, DFS)이란? 탐색을 할 때 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다

---

깊이 우선 탐색(Depth First Search, DFS)

1️⃣ 깊이 우선 탐색이란?

• 탐색을 할 때 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다
• 전체 노드를 맹목적ㅡ로 탐색하고자 할 때 사용한다
• 깊이 우선 탐색 알고리즘은 스택(stack) 자료구조에 기초한다
• 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있다

✔️ 깊이 우선 탐색의 원리

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다
2) 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다

• 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3) 2)번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다

💡 방문 순서 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

• 깊이 우선 탐색 알고리즘은 스택(stack) 자료구조에 기초한다는 점에서 구현이 간단하다
• 실제로는 스택을 쓰지 않아도 되며
• 탐색을 수행함에 있어서 𝑂(𝑁)의 시간이 소요된다

---

✨ tl;dr

• 깊이 우선 탐색은 𝑂(𝑁)의 시간이 소요되는 전수 탐색 알고리즘이다