BFS (너비 우선 탐색)

관련 문제

문제	난이도	핵심
1260번 — DFS와 BFS	실버 II	BFS 기본 구현
2178번 — 미로 탐색	실버 I	최단 거리
7569번 — 토마토	골드 V	3차원 BFS
7576번 — 토마토	실버 I	다중 출발 BFS
2206번 — 벽 부수고 이동하기	골드 IV	상태 BFS

---

1. 개념

BFS(Breadth-First Search, 너비 우선 탐색)는 시작 노드에서 가까운 노드부터 순서대로 탐색하는 알고리즘이다.

거리가 1인 노드를 모두 탐색하고, 그 다음 거리 2인 노드를 탐색한다.

큐(Queue)를 사용해 구현하며, 최단 거리/최소 횟수 문제에서 DFS보다 BFS가 적합하다.

DFS = 깊이 우선, 재귀/스택
BFS = 너비 우선, 큐(Queue)

---

2. 동작 과정

아래 그래프에서 1번 노드부터 BFS 탐색

1 - 2 - 4
|   |
3   5

단계	큐 상태	꺼낸 노드	방문 처리	큐에 추가
1	[1]	1	✅	2, 3
2	[2, 3]	2	✅	4, 5
3	[3, 4, 5]	3	✅	없음
4	[4, 5]	4	✅	없음
5	[5]	5	✅	없음

탐색 순서: 1 → 2 → 3 → 4 → 5

---

3. DFS vs BFS

	DFS	BFS
자료구조	스택 / 재귀	큐
탐색 방향	깊이 우선	너비 우선
최단 거리 보장	❌	✅
적합한 문제	경로 존재 여부, 백트래킹	최단 거리, 최소 횟수

가중치 없는 그래프에서 최단 경로는 반드시 BFS를 써야 한다.
BFS는 먼저 꺼낸 노드가 항상 더 가까운 거리이기 때문이다.

---

4. 핵심 포인트 2가지

큐에 넣을 때 visited 처리를 해야 한다

꺼낼 때가 아닌 넣을 때 방문 처리를 해야 한다.
꺼낼 때 처리하면 같은 노드가 큐에 중복으로 들어가 불필요한 탐색이 발생한다.

// ❌ 잘못된 방식 — 꺼낼 때 처리
int cur = queue.poll();
visited[cur] = true;

// ✅ 올바른 방식 — 넣을 때 처리
visited[next] = true;
queue.add(next);

최단 거리는 dist 배열로 관리한다

BFS는 레벨(거리) 순서로 탐색하므로, 처음 도달한 거리가 곧 최단 거리다.
별도 dist 배열을 두고 dist[next] = dist[cur] + 1로 갱신한다.

---

5. 코드

인접 리스트 방식

static boolean[] visited;
static List<List<Integer>> graph;

static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;   // 넣을 때 방문 처리
    queue.add(start);

    while (!queue.isEmpty()) {
        int cur = queue.poll();

        for (int next : graph.get(cur)) {
            if (!visited[next]) {
                visited[next] = true;   // 넣을 때 방문 처리
                queue.add(next);
            }
        }
    }
}

격자(2차원 배열) + 최단 거리

static int[][] dist;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};  // 상하좌우
static int[] dy = {0, 0, -1, 1};
static int N, M;

static void bfs(int sx, int sy) {
    Queue<int[]> queue = new LinkedList<>();
    visited[sx][sy] = true;
    dist[sx][sy] = 0;
    queue.add(new int[]{sx, sy});

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int x = cur[0], y = cur[1];

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M   // 범위 체크
                    && !visited[nx][ny] && map[nx][ny] == 1) {
                visited[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;           // 최단 거리 갱신
                queue.add(new int[]{nx, ny});
            }
        }
    }
}

---

6. 시간복잡도

그래프 표현	시간복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

DFS와 시간복잡도는 같다. 차이는 탐색 순서와 최단 거리 보장 여부다.

---

7. 주의사항

• visited는 큐에 넣을 때 처리한다. 꺼낼 때 처리하면 같은 노드가 큐에 중복으로 쌓여 시간 초과가 날 수 있다.
• 다중 출발 BFS: 시작점이 여러 개인 문제(토마토 등)는 모든 시작점을 큐에 미리 넣고 BFS를 시작한다.
• 격자 문제 범위 체크: nx, ny 범위를 visited와 값 체크보다 먼저 해야 한다. 순서가 바뀌면 ArrayIndexOutOfBoundsException이 발생한다.
• dist 초기화: dist 배열은 기본값이 0이므로, 시작점과 미방문 노드를 구분하려면 -1로 초기화하거나 visited 배열을 함께 사용하라.