[알고리즘] 29. BFS 너비 우선 탐색
지난 글에서는 DFS 깊이 우선 탐색에 대해 정리했습니다. 이번 글에서는 그래프 탐색에서 DFS와 함께 가장 많이 등장하는 BFS에 대해 알아보겠습니다.
BFS는 Breadth First Search의 줄임말로, 우리말로는 너비 우선 탐색이라고 합니다. DFS가 한 방향으로 깊게 들어가는 방식이라면, BFS는 시작점에서 가까운 곳부터 차례대로 탐색하는 방식입니다.
BFS는 시작점에서 가까운 정점부터 차례대로 방문하는 탐색 알고리즘입니다.
1. BFS란?
BFS는 그래프나 트리에서 시작 정점과 가까운 정점부터 먼저 방문하는 탐색 방법입니다. 한 정점에서 바로 갈 수 있는 곳을 먼저 모두 확인하고, 그다음 거리의 정점을 확인합니다.
1
/ \
2 3
/ \ \
4 5 6위 구조에서 1번부터 BFS를 시작하면 보통 다음 순서로 방문합니다.
1 → 2 → 3 → 4 → 5 → 6먼저 시작점 1을 방문합니다. 그다음 1과 가까운 2, 3을 방문하고, 이후 2와 3에서 이어지는 4, 5, 6을 방문합니다.
BFS의 핵심은 가까운 곳부터 넓게 퍼지듯이 탐색하는 것입니다.
2. BFS가 필요한 상황
BFS는 가까운 위치부터 순서대로 탐색해야 하는 문제에서 자주 사용됩니다. 특히 최단 거리 문제에서 많이 등장합니다.
- 그래프의 모든 정점 방문하기
- 시작점에서 가장 가까운 정점부터 탐색하기
- 최단 거리 구하기
- 미로에서 최소 이동 횟수 구하기
- 2차원 지도에서 퍼지는 과정 표현하기
- 감염, 전파, 확산 문제 처리하기
- 레벨별 탐색이 필요한 문제 해결하기
문제를 보고 “가장 적은 이동 횟수”, “가장 가까운 거리”, “동시에 퍼져나감” 같은 표현이 보이면 BFS를 의심해볼 수 있습니다.
3. BFS의 기본 흐름
BFS의 기본 흐름은 다음과 같습니다.
- 시작 정점을 큐에 넣는다.
- 시작 정점을 방문 처리한다.
- 큐에서 정점을 하나 꺼낸다.
- 꺼낸 정점과 연결된 정점을 확인한다.
- 아직 방문하지 않은 정점이면 방문 처리하고 큐에 넣는다.
- 큐가 빌 때까지 반복한다.
시작점 큐에 넣기
→ 큐에서 꺼내기
→ 연결된 정점 확인
→ 방문하지 않았다면 큐에 넣기
→ 큐가 빌 때까지 반복BFS는 큐(Queue)를 사용합니다. 큐는 먼저 들어온 값이 먼저 나가는 선입선출 구조이기 때문에, 가까운 정점부터 차례대로 처리하기 좋습니다.
BFS는 큐를 이용해 먼저 발견한 정점부터 차례대로 탐색합니다.
4. DFS와 BFS 비교
DFS와 BFS는 모두 그래프 탐색 알고리즘입니다. 하지만 탐색 방향과 사용하는 자료구조가 다릅니다.
| 구분 | DFS | BFS |
|---|---|---|
| 탐색 방식 | 한 방향으로 깊게 탐색 | 가까운 곳부터 넓게 탐색 |
| 주요 구현 | 재귀, 스택 | 큐 |
| 방문 흐름 | 깊게 들어갔다가 되돌아옴 | 거리순으로 차례대로 퍼짐 |
| 대표 사용 | 경로 탐색, 연결 요소, 백트래킹 | 최단 거리, 레벨 탐색, 확산 문제 |
DFS는 깊게 파고드는 느낌이고, BFS는 물결처럼 퍼지는 느낌입니다. 최단 거리를 구해야 하는 문제에서는 BFS가 자주 사용됩니다.
5. BFS에서 큐가 필요한 이유
BFS는 먼저 발견한 정점부터 처리해야 합니다. 이를 위해 큐를 사용합니다.
1번 방문
1과 연결된 2, 3을 큐에 넣음
큐에서 2를 먼저 꺼냄
큐에서 3을 다음으로 꺼냄큐는 먼저 들어온 값이 먼저 나옵니다. 그래서 먼저 발견한 정점을 먼저 탐색하는 BFS 흐름과 잘 맞습니다.
Queue: [2, 3]
poll() → 2
poll() → 3BFS는 큐 없이는 순서 관리가 어려운 탐색 알고리즘입니다.
6. 방문 배열이 필요한 이유
BFS에서도 DFS와 마찬가지로 방문 배열이 필요합니다. 그래프에 사이클이 있을 수 있기 때문입니다.
1 --- 2
| |
3 --- 4방문 체크를 하지 않으면 1에서 2로 가고, 2에서 다시 1로 돌아오는 식으로 같은 정점을 계속 큐에 넣을 수 있습니다. 그러면 탐색이 끝나지 않거나 불필요한 반복이 많아집니다.
boolean[] visited = new boolean[n + 1];정점을 큐에 넣을 때 방문 처리까지 함께 해주는 것이 안전합니다.
BFS에서는 큐에 넣는 순간 방문 처리하는 방식이 안전합니다.
7. 인접 리스트로 그래프 만들기
BFS를 구현하려면 먼저 그래프의 연결 정보를 저장해야 합니다. 정점 수가 많을 때는 보통 인접 리스트를 사용합니다.
다음 그래프를 예로 보겠습니다.
1 --- 2
| |
3 --- 4연결 관계는 다음과 같습니다.
| 정점 | 연결된 정점 |
|---|---|
| 1 | 2, 3 |
| 2 | 1, 4 |
| 3 | 1, 4 |
| 4 | 2, 3 |
Java에서는 ArrayList 배열로 인접 리스트를 만들 수 있습니다.
import java.util.ArrayList;
int n = 4;
ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
graph[1].add(2);
graph[2].add(1);
graph[1].add(3);
graph[3].add(1);
graph[2].add(4);
graph[4].add(2);
graph[3].add(4);
graph[4].add(3);무방향 그래프이므로 양쪽 방향을 모두 저장했습니다.
8. BFS 기본 코드
BFS의 기본 코드는 다음과 같습니다.
import java.util.LinkedList;
import java.util.Queue;
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.println(current);
for (int next : graph[current]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}코드 흐름은 다음과 같습니다.
- 시작 정점을 큐에 넣고 방문 처리한다.
- 큐가 빌 때까지 반복한다.
- 큐에서 현재 정점을 꺼낸다.
- 현재 정점과 연결된 정점을 확인한다.
- 방문하지 않은 정점이면 방문 처리하고 큐에 넣는다.
9. BFS 전체 예제 코드
이번에는 그래프 생성부터 BFS 실행까지 전체 코드를 보겠습니다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void main(String[] args) {
int n = 4;
graph = new ArrayList[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(3, 4);
bfs(1);
}
public static void addEdge(int a, int b) {
graph[a].add(b);
graph[b].add(a);
}
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.println(current);
for (int next : graph[current]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}
}출력 결과는 인접 리스트에 값을 넣은 순서에 따라 달라질 수 있습니다. 위 코드에서는 다음과 같이 출력됩니다.
1
2
3
41번에서 시작해서 가까운 2번과 3번을 먼저 방문하고, 그다음 4번을 방문합니다.
BFS 방문 순서는 큐에 어떤 정점이 먼저 들어갔는지에 따라 결정됩니다.
10. BFS 동작 과정 예시
아래 그래프에서 1번 정점부터 BFS를 시작한다고 하겠습니다.
1 --- 2
| |
3 --- 4인접 리스트가 다음 순서라고 가정합니다.
1: 2, 3
2: 1, 4
3: 1, 4
4: 2, 3BFS 동작 흐름은 다음과 같습니다.
| 단계 | 큐 상태 | 꺼낸 정점 | 새로 넣는 정점 |
|---|---|---|---|
| 초기 | [1] | - | 1 방문 처리 |
| 1 | [2, 3] | 1 | 2, 3 |
| 2 | [3, 4] | 2 | 4 |
| 3 | [4] | 3 | 없음 |
| 4 | [] | 4 | 없음 |
방문 순서는 1 → 2 → 3 → 4입니다. 이미 방문한 정점은 큐에 다시 넣지 않습니다.
11. BFS로 최단 거리 구하기
BFS는 간선의 가중치가 모두 같은 그래프에서 최단 거리를 구할 때 매우 유용합니다. 시작점에서 가까운 정점부터 탐색하기 때문입니다.
거리 정보를 저장하기 위해 distance 배열을 사용할 수 있습니다.
int[] distance = new int[n + 1];처음에는 방문하지 않았다는 의미로 -1을 넣어둘 수 있습니다.
import java.util.Arrays;
Arrays.fill(distance, -1);시작 정점의 거리는 0입니다. 그리고 다음 정점을 방문할 때 현재 거리보다 1 큰 값을 저장합니다.
distance[next] = distance[current] + 1BFS는 가까운 곳부터 방문하기 때문에 처음 도착한 거리가 최단 거리입니다.
12. 최단 거리 BFS 코드
BFS로 시작 정점에서 각 정점까지의 최단 거리를 구하는 코드는 다음과 같습니다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
static int[] distance;
public static void bfsDistance(int start) {
Queue<Integer> queue = new LinkedList<>();
Arrays.fill(distance, -1);
queue.offer(start);
distance[start] = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : graph[current]) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
queue.offer(next);
}
}
}
}visited 배열 대신 distance 배열을 방문 여부처럼 사용할 수도 있습니다. distance[next]가 -1이면 아직 방문하지 않은 정점입니다.
예를 들어 1번에서 시작했을 때 결과가 아래와 같을 수 있습니다.
distance[1] = 0
distance[2] = 1
distance[3] = 1
distance[4] = 21번에서 4번까지는 2번 또는 3번을 거쳐 가야 하므로 거리가 2입니다.
13. 2차원 배열에서 BFS
BFS는 2차원 배열에서도 자주 사용됩니다. 대표적인 예가 미로에서 최단 거리 구하기입니다.
1 1 0
0 1 1
0 0 11은 이동 가능한 칸, 0은 이동할 수 없는 칸이라고 생각할 수 있습니다. 상하좌우로 이동하면서 목적지까지의 최소 이동 횟수를 구할 때 BFS를 사용합니다.
2차원 BFS에서는 방향 배열을 사용합니다.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};위 배열은 상, 하, 좌, 우 이동을 의미합니다.
14. 2차원 BFS 기본 코드
2차원 배열에서 BFS를 구현하면 다음과 같습니다.
import java.util.LinkedList;
import java.util.Queue;
static int[][] map;
static boolean[][] visited;
static int n;
static int m;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void bfs(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {startX, startY});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
visited[nx][ny] = true;
queue.offer(new int[] {nx, ny});
}
}
}2차원 BFS에서는 다음 세 가지 체크가 중요합니다.
- 배열 범위를 벗어나지 않는가?
- 이미 방문한 칸인가?
- 이동 가능한 칸인가?
2차원 BFS에서는 범위 체크, 방문 체크, 이동 가능 여부 체크가 핵심입니다.
15. BFS의 시간복잡도
그래프 BFS는 모든 정점과 간선을 한 번씩 확인합니다. 정점 수를 V, 간선 수를 E라고 하면 시간복잡도는 보통 O(V + E)입니다.
| 구분 | 의미 |
|---|---|
| V | 정점의 개수 |
| E | 간선의 개수 |
| BFS 시간복잡도 | O(V + E) |
2차원 배열 BFS에서는 모든 칸을 한 번씩 확인한다고 생각하면 됩니다. 행의 개수를 N, 열의 개수를 M이라고 하면 시간복잡도는 O(N × M)입니다.
BFS도 방문 체크를 제대로 하면 각 정점이나 칸을 보통 한 번씩만 방문합니다.
16. BFS에서 자주 하는 실수
BFS 문제를 풀 때는 아래 실수를 조심해야 합니다.
- 큐를 사용하지 않고 순서를 잘못 처리하는 경우
- 방문 처리를 큐에서 꺼낼 때 해서 중복으로 큐에 들어가는 경우
- 무방향 그래프에서 간선을 한쪽만 저장하는 경우
- 2차원 배열에서 범위 체크를 하지 않는 경우
- 이미 방문한 위치를 다시 큐에 넣는 경우
- 최단 거리 문제에서 DFS를 사용하려는 경우
- 가중치가 있는 그래프에서 일반 BFS로 최단 거리를 구하려는 경우
특히 BFS에서는 방문 처리를 큐에 넣는 순간 하는 것이 안전합니다. 그래야 같은 정점이 큐에 여러 번 들어가는 일을 막을 수 있습니다.
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}BFS 실수의 대부분은 방문 처리 시점과 큐 관리에서 발생합니다.
17. 정리
이번 글에서는 BFS에 대해 정리했습니다.
- BFS는 너비 우선 탐색이다.
- 시작점에서 가까운 정점부터 차례대로 방문한다.
- BFS는 큐를 이용해 구현한다.
- 큐에 넣는 순간 방문 처리하는 것이 안전하다.
- 그래프 탐색에서는 방문 배열이 필요하다.
- 간선의 가중치가 모두 같다면 BFS로 최단 거리를 구할 수 있다.
- 2차원 배열에서는 상하좌우 방향 배열을 자주 사용한다.
- 그래프 BFS의 시간복잡도는 O(V + E)이다.
- 2차원 배열 BFS의 시간복잡도는 O(N × M)이다.
BFS는 그래프 탐색에서 매우 중요한 알고리즘입니다. DFS가 깊게 들어가는 탐색이라면, BFS는 가까운 곳부터 차례대로 퍼져나가는 탐색입니다. 특히 최단 거리 문제에서는 BFS가 자주 사용되므로 큐와 방문 배열 흐름을 정확히 익혀두는 것이 좋습니다.
BFS의 핵심은 큐를 사용해 가까운 곳부터 차례대로 탐색하는 것입니다.
다음 글 예고
다음 글에서는 방문 배열에 대해 더 자세히 알아보겠습니다.
DFS와 BFS에서 방문 배열이 왜 필요한지, 언제 방문 처리해야 하는지, 그래프와 2차원 배열에서 visited를 어떻게 사용하는지 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 31. 격자 탐색 (0) | 2026.07.14 |
|---|---|
| [알고리즘] 30. 방문 배열 (0) | 2026.07.13 |
| [알고리즘] 28. DFS 깊이 우선 탐색 (1) | 2026.07.11 |
| [알고리즘] 27. 이분 탐색 응용 (0) | 2026.07.10 |
| [알고리즘] 26. 이분 탐색 기초 (0) | 2026.07.09 |