[알고리즘] BFS(너비 우선 탐색)란 무엇인가? (백준 2606, 2178)

📌 핵심 요약

• BFS(너비 우선 탐색)는 시작점에서 가까운 곳부터 차례대로 퍼져나가며 탐색하는 알고리즘입니다.
• 탐색 순서를 관리하기 위해 큐(Queue) 자료구조를 사용하며, 먼저 발견한 노드를 먼저 방문합니다.
• 모든 간선의 비용이 같을 때(가중치가 없을 때) 최단 거리를 보장하는 것이 BFS의 가장 큰 강점입니다.
• 백준 2606(바이러스), 2178(미로 탐색) 두 문제로 연결 요소 탐색과 최단 거리 계산을 직접 풀어봅니다.

 

목차

1 BFS(너비 우선 탐색)란?

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리에서 시작점과 가까운 노드부터 차례대로 방문하는 탐색 알고리즘입니다.

호수에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가는 모습을 떠올리면 됩니다.

시작점에서 거리 1인 노드를 모두 방문한 뒤, 거리 2인 노드, 거리 3인 노드… 순서로 한 겹씩(너비 단위로) 탐색 범위를 넓혀갑니다.

그래프란?

BFS를 이해하려면 먼저 그래프가 무엇인지 알아야 합니다.

그래프(Graph)는 노드(정점)와 노드 사이를 연결하는 간선(선)으로 이루어진 자료구조입니다.

지하철 노선도를 생각하면 쉽습니다. 각 역이 노드, 역과 역을 잇는 선로가 간선입니다. 컴퓨터 네트워크, SNS 친구 관계, 미로의 길 등 “무언가와 무언가가 연결된 구조”는 대부분 그래프로 표현할 수 있습니다.

왜 큐(Queue)를 사용할까?

큐(Queue)는 먼저 넣은 데이터가 먼저 나오는(FIFO, First-In First-Out) 자료구조입니다. 은행 창구의 대기줄처럼, 먼저 줄을 선 사람이 먼저 처리됩니다.

BFS가 큐를 사용하는 이유는 “먼저 발견한 노드를 먼저 방문해야” 가까운 순서대로 탐색이 진행되기 때문입니다.

시작점에서 거리 1인 노드들을 큐에 넣으면, 그 노드들을 꺼내 처리하는 동안 거리 2인 노드들이 큐의 뒤에 쌓입니다.

큐는 항상 앞에서부터 꺼내므로 거리 1이 모두 끝난 뒤에야 거리 2가 처리됩니다.

이 성질 덕분에 BFS는 자연스럽게 가까운 순서대로 탐색하게 되고, 가중치가 없는 그래프에서 최단 거리를 보장하게 됩니다.

ℹ️

스택을 쓰면 DFS가 됩니다

같은 코드에서 큐 대신 스택(나중에 넣은 것이 먼저 나오는 구조)을 쓰면, 한 방향으로 끝까지 파고드는 DFS(깊이 우선 탐색)가 됩니다. 즉 어떤 자료구조로 “다음에 방문할 노드”를 관리하느냐가 BFS와 DFS를 가르는 핵심입니다.

2 BFS의 동작 원리

BFS는 큐와 방문 체크 배열(visited) 두 가지만 있으면 동작합니다. 전체 흐름은 아래 4단계의 반복입니다.

BFS 동작 4단계

1. 시작 노드를 큐에 넣고, 방문 처리(visited = true)합니다.
2. 큐에서 노드를 하나 꺼냅니다(poll).
3. 꺼낸 노드와 연결된 인접 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣고, 넣는 순간 방문 처리합니다.
4. 큐가 빌 때까지 2~3번을 반복합니다. 큐가 비면 시작점에서 도달 가능한 모든 노드를 방문한 것입니다.

⚠️

방문 처리는 “큐에 넣을 때” 해야 합니다

큐에서 꺼낼 때 방문 처리를 하면, 같은 노드가 여러 경로를 통해 큐에 중복으로 들어가는 문제가 생깁니다. 노드 수가 많은 문제에서는 이 중복 때문에 메모리 초과나 시간 초과가 발생할 수 있으니, 반드시 큐에 넣는 순간 방문 처리하는 습관을 들이세요.

3 BFS vs DFS 비교

BFS와 DFS는 모두 그래프의 모든 노드를 한 번씩 방문하는 완전 탐색 알고리즘이라 시간 복잡도는 같습니다.

하지만 탐색 순서가 다르기 때문에 문제 유형에 따라 유리한 쪽이 달라집니다.

구분	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	가까운 노드부터 한 겹씩 확장	한 방향으로 끝까지 파고든 후 되돌아옴
사용 자료구조	큐 (Queue)	스택 (Stack) 또는 재귀
최단 거리 보장	보장 (가중치 없을 때)	보장 안 됨
시간 복잡도	O(V + E)	O(V + E)
유리한 문제	최단 거리, 최소 횟수, 가까운 대상 찾기	모든 경로 탐색, 백트래킹, 사이클 판별

💡

문제에서 “최단”, “최소”가 보이면 BFS

“최단 거리”, “최소 이동 횟수”, “최소 몇 번 만에” 같은 표현이 등장하고 간선의 비용이 모두 같다면 BFS를 먼저 떠올리세요. 반대로 간선마다 비용(가중치)이 다르다면 다익스트라 알고리즘이 필요합니다.

4 Java로 BFS 구현하기

그래프를 인접 리스트(각 노드마다 “연결된 노드 목록”을 저장하는 방식)로 표현하고, 자바의 Queue 인터페이스와 LinkedList 구현체로 BFS 기본 뼈대를 작성해 보겠습니다. 이 뼈대는 거의 모든 BFS 문제에서 그대로 재사용됩니다.

 

Java — BFS 기본 템플릿

import java.util.*;

public class BfsTemplate {

    // graph[i] = i번 노드와 연결된 노드 목록 (인접 리스트)
    static List<Integer>[] graph;
    static boolean[] visited;

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();

        // 1. 시작 노드를 큐에 넣고, 넣는 순간 방문 처리
        queue.offer(start);
        visited[start] = true;

        // 4. 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 2. 큐에서 노드를 하나 꺼낸다
            int cur = queue.poll();
            System.out.println("방문: " + cur);

            // 3. 인접 노드 중 미방문 노드를 큐에 넣는다
            for (int next : graph[cur]) {
                if (!visited[next]) {
                    visited[next] = true; // 넣는 순간 방문 처리!
                    queue.offer(next);
                }
            }
        }
    }
}

ℹ️

offer / poll 메서드

offer()는 큐의 뒤에 데이터를 넣는 메서드, poll()은 큐의 앞에서 데이터를 꺼내는 메서드입니다. 비슷한 역할의 add() / remove()도 있지만, 이 둘은 실패 시 예외를 던지는 반면 offer() / poll()은 null 등을 반환하므로 알고리즘 문제에서는 보통 offer() / poll()을 사용합니다.

5 문제풀이 1 : 백준 2606 바이러스

첫 번째 문제는 BFS 입문 문제의 대표 격인 바이러스입니다. “시작점에서 도달할 수 있는 노드가 몇 개인가”를 세는 연결 요소 탐색 유형으로, 앞에서 만든 기본 템플릿을 거의 그대로 사용할 수 있습니다.

BOJ #2606

바이러스

컴퓨터 수 ≤ 100 · 시간제한 1초

난이도: Silver III

컴퓨터들이 네트워크로 연결되어 있습니다. 1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 출력하는 문제입니다. (1번 자신은 제외)

풀이 과정

1. 컴퓨터를 노드, 네트워크 연결을 간선으로 보고 인접 리스트로 그래프를 만든다. 연결은 양방향이므로 간선을 양쪽 모두에 추가한다.
2. 1번 노드에서 BFS를 시작해 도달 가능한 모든 노드를 방문한다.
3. 방문한 노드 수를 세고, 시작점인 1번을 제외하기 위해 결과에서 1을 뺀다.

 

Java — 백준 2606 바이러스

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 컴퓨터(노드) 수
        int m = sc.nextInt(); // 연결(간선) 수

        // 인접 리스트 초기화 (1번 노드부터 쓰기 위해 n+1 크기)
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        // 양방향 간선 등록
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        // 1번 노드에서 BFS
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        int count = 0; // 감염된 컴퓨터 수 (1번 제외)

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph[cur]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                    count++; // 새로 감염될 때마다 카운트
                }
            }
        }

        System.out.println(count);
    }
}

💡

1번을 방문 처리한 뒤 count는 0에서 시작

시작점 1번을 큐에 넣을 때 count를 올리지 않고, 새로운 노드가 감염될 때만 count를 올리면 “1번을 제외한 감염 컴퓨터 수”가 자연스럽게 계산됩니다. 마지막에 1을 빼는 방식보다 실수할 여지가 적습니다.

6 문제풀이 2 : 백준 2178 미로 탐색

두 번째 문제는 BFS의 진짜 강점인 최단 거리를 활용하는 미로 탐색입니다. 이번에는 노드가 번호가 아니라 2차원 격자의 칸(행, 열)이라는 점이 다릅니다. 격자 문제에서는 상하좌우 이동을 표현하는 방향 배열(dx, dy) 기법을 사용합니다.

BOJ #2178

미로 탐색

N, M ≤ 100 · 시간제한 1초

난이도: Silver I

N×M 크기의 미로에서 (1, 1)에서 출발해 (N, M)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 문제입니다. 1은 이동 가능한 칸, 0은 벽이며, 시작 칸과 도착 칸도 개수에 포함됩니다.

풀이 과정

1. “최소 칸 수”를 묻고 모든 이동 비용이 1로 같으므로 BFS로 최단 거리를 구하면 된다.
2. 상하좌우 이동을 dx, dy 방향 배열로 표현하고, 미로 범위를 벗어나거나 벽(0)이거나 이미 방문한 칸은 건너뛴다.
3. 거리 저장은 별도 배열 대신 미로 배열 값 자체를 누적 거리로 갱신한다. 다음 칸의 값 = 현재 칸의 값 + 1.
4. 탐색이 끝나면 도착 칸 (N, M)에 저장된 값이 최단 거리(지나온 칸 수)가 된다.

 

Java — 백준 2178 미로 탐색

import java.io.*;
import java.util.*;

public class Main {
    // 상, 하, 좌, 우 네 방향 (dx = 행 이동, dy = 열 이동)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                maze[i][j] = line.charAt(j) - '0';
            }
        }

        // BFS : 큐에는 {행, 열} 좌표를 int 배열로 담는다
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

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

            // 네 방향을 모두 확인
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                // 미로 범위 밖이면 건너뛰기
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                // 벽이거나 이미 방문한 칸이면 건너뛰기
                if (maze[nx][ny] == 0 || visited[nx][ny]) continue;

                visited[nx][ny] = true;
                // 다음 칸의 거리 = 현재 칸의 거리 + 1
                maze[nx][ny] = maze[x][y] + 1;
                queue.offer(new int[]{nx, ny});
            }
        }

        // 도착 칸에 누적된 값 = 지나온 최소 칸 수
        System.out.println(maze[n - 1][m - 1]);
    }
}

⚠️

BFS의 최단 거리는 “처음 도착한 순간” 확정됩니다

BFS는 가까운 칸부터 순서대로 방문하기 때문에, 어떤 칸에 처음 도착했을 때의 거리가 곧 최단 거리입니다. 그래서 이미 방문한 칸은 다시 볼 필요가 없고, DFS처럼 모든 경로를 비교할 필요도 없습니다. 이것이 최단 거리 문제에서 BFS를 쓰는 이유입니다.

7 마무리

BFS의 핵심을 다시 정리하면 세 가지입니다. 큐를 사용해 가까운 노드부터 방문한다, 큐에 넣는 순간 방문 처리한다, 가중치가 없다면 최단 거리가 보장된다. 이 세 가지만 기억하면 기본 템플릿에서 “큐에 무엇을 담을지(노드 번호 or 좌표)”와 “무엇을 셀지(개수 or 거리)”만 바꿔가며 대부분의 BFS 문제를 풀 수 있습니다.

💡

다음 단계 추천 문제

백준 1926(그림), 7576(토마토), 1697(숨바꼭질)을 추천합니다. 특히 토마토는 시작점이 여러 개인 멀티 소스 BFS, 숨바꼭질은 격자가 아닌 수직선 위의 BFS로, 오늘 배운 템플릿을 응용하는 좋은 연습이 됩니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.