🚀 What I Will Learn

• 너비 우선 탐색(Breadth First Search, BFS)에 대해 이해하기

너비 우선 탐색(Breadth First Search, BFS)이란? 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

---

너비 우선 탐색(Breadth First Search, BFS)

1️⃣ 너비 우선 탐색이란?

• 너비를 우선으로 하여 탐색을 수행하는 알고리즘
• DFS와 마찬가지로, 맹목적으로 전체 노드를 탐색하고자 할 때 자주 사용
• 큐(Queue) 자료구조에 기초
• 고급 그래프 탐색 알고리즘에서 자주 활용되므로 고급 개발자가 되기 위해서는 너비 우선 탐색에 대해 숙지해야 한다👍

✔️ 너비 우선 탐색의 원리

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문 처리를 한다
3) 2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

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

• 너비 우선 탐색 알고리즘은 큐(Queue) 자료구조에 기초한다는 점에서 구현이 간단하다
• 실제로는 큐 STL을 사용하면 좋으며
• 탐색할 때 𝑂(𝑁)의 시간이 소요된다
• 일반적인 경우, 실제 수행 시간은 DFS보다 좋다

---

✨ tl;dr

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