BFS(breadth-first search) 너비 우선 탐색

 

그래프 문제를 풀다 보면 깊이 우선 탐색(DFS)와 함께 반드시 등장하는 탐색 알고리즘이 너비 우선 탐색(BFS)이다.
BFS 역시 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 알고리즘 중 하나로, 시작 노드를 기준으로 가까운 노드부터 차례대로 탐색하는 방식이 특징이다.

이번 글에서는 BFS의 개념과 특징, 구현 방식, 시간 복잡도, 그리고 DFS와 다른 점까지 간단히 정리해보려고 한다. ✍️

 

DFS 관련 내용은 다음 링크를 참고하면 좋습니다!

https://xeungcoding.tistory.com/25

DFS(depth-first search) 깊이 우선 탐색

 

 

---

 

 

너비 우선 탐색이란?

너비 우선 탐색(BFS, Breadth-First Search)은 그래프의 시작 노드에서 출발하여, 시작 노드와 가까운 노드부터 차례대로 방문하며 탐색하는 알고리즘이다.

 

DFS가 한 방향으로 깊게 들어가는 방식이라면,
BFS는 같은 깊이(거리)에 있는 노드들을 먼저 탐색한 뒤 다음 단계로 넘어간다.

 

즉,

• 시작 노드를 먼저 방문하고
• 시작 노드와 인접한 노드들을 모두 방문한 뒤
• 그 다음 깊이의 노드들을 순서대로 탐색한다

이러한 특성 때문에 BFS는 “가까운 곳부터 넓게 퍼져 나가는 탐색 🔁 ” 흐름을 가진다. 

 

 

---

 

 

BFS의 동작 방식과 구현 특징🔧

BFS는 선입선출(FIFO) 방식으로 탐색이 이루어진다.
이 때문에 BFS는 큐(Queue) 자료구조를 이용해 구현한다.

 

큐(Queue)를 사용하는 이유

• 먼저 방문한 노드를 먼저 탐색해야 하기 때문
• 탐색 순서가 방문 순서와 동일하게 유지됨

BFS의 가장 큰 특징 중 하나는 탐색 시작 노드에서 목표 노드까지의 최단 경로를 보장한다는 점이다.

그래프에서 목표 노드로 가는 경로가 여러 개일 경우, BFS는 가장 먼저 도달한 경로가 가장 짧은 경로가 된다. ⭐

이 때문에 BFS는 최단 거리, 최소 이동 횟수를 구하는 문제에서 자주 사용된다.

 

BFS의 원리 (탐색 과정) 📌

BFS의 기본적인 동작 과정은 다음과 같다.

이 과정에서도 DFS와 마찬가지로 이미 방문한 노드를 다시 방문하지 않도록 방문 체크가 필수이다. 

1. BFS를 시작할 노드를 정한 후, 사용할 자료구조(큐)를 초기화한다.
2. 큐에서 노드를 하나 꺼낸 뒤, 해당 노드와 인접한 노드들을 다시 큐에 삽입한다.
3. 큐에 더 이상 값이 없을 때까지 이 과정을 반복한다.

 

시간 복잡도⏰

노드의 개수를 V, 에지(간선)의 개수를 E라고 할 때 BFS의 시간 복잡도는 다음과 같다.

O(V + E)

• 모든 노드를 한 번씩 방문하고
• 모든 간선을 한 번씩 확인하기 때문이다.

DFS와 동일한 시간 복잡도를 가지지만, 탐색 순서와 활용 목적은 확실히 다르다.

 

 

---

 

 

BFS로 풀 수 있는 대표적인 문제들

최단 경로 탐색

• 미로 탐색
• 최소 이동 횟수 문제
• 숨바꼭질 유형 문제

레벨 탐색

• 트리의 레벨별 탐색
• 단계별 확산 문제 (전염, 퍼짐 등)

그래프 탐색

• 연결 요소 개수 구하기
• 특정 거리 이내 노드 찾기

 

+ 아래 문제들을 풀어 보시면 좋습니다!
https://www.acmicpc.net/workbook/view/1833