알고리즘 기초 - 너비 우선 탐색(BFS)

---

BFS란?

---

• 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 가까운 노드부터 차례대로 탐색해 나가는 방식입니다.
• 즉, "넓게 퍼져나가듯" 탐색한다고 해서 너비 우선 탐색이라고 부릅니다.

 

동작 원리

1. 시작 노드를 큐(Queue)에 넣는다.
2. 큐에서 노드를 꺼내서 방문한다.
3. 방문한 노드의 인접한 노드들을 모두 큐에 넣는다.
4. 큐가 빌 때까지 2~3 과정을 반복한다.

 

---

BFS의 특징

---

 

큐(Queue) 사용: FIFO 구조로 탐색 순서를 보장
가까운 노드부터 탐색: 레벨별 탐색이 가능
최단 경로 탐색에 유리: 가중치가 없는 그래프에서 최단 거리를 찾을 때 많이 사용

 

---

마무리

---

BFS는 그래프나 트리에서 가장 기본적인 탐색 알고리즘으로,
큐를 활용해 가까운 노드부터 차례대로 탐색하는 방식입니다.
특히 최단 거리 문제에서 매우 유용하게 사용되므로 꼭 알아두어야 합니다!