[알고리즘] BFS 개념 정리 (+ 백준 1260)

🔍 BFS(Breadth-First Search) 완전 정복

 

코딩테스트의 기본 탐색 알고리즘

 

그래프 탐색 문제에서 DFS와 함께 항상 등장하는 알고리즘이 BFS(너비 우선 탐색).

특히 BFS는 가장 가까운 노드부터 탐색하는 특성 덕분에 최단 거리 문제에서 자주 사용되는 방식.

 

 

---

 

✅ BFS란?

 

BFS(Breadth-First Search)는 시작 노드로부터 가까운 순서대로 탐색하는 그래프 탐색 기법

같은 깊이의 노드들을 먼저 방문한 뒤, 점점 더 멀리 있는 노드를 탐색하는 방식

 

DFS가 깊게 내려가는 구조라면, BFS는 넓게 펼쳐지며 탐색하는 구조라고 이해하면 쉬운 형태

 

---

 

✔ 핵심 특징

 

• 큐(Queue) 자료구조 사용
• 방문한 노드를 체크하기 위한 방문 배열 필요
• 모든 정점을 한 번씩 방문하며 모든 간선을 확인
• 시간복잡도: O(V + E)
• 그래프는 인접 리스트로 표현하는 것이 효율적인 방식

 

---

 

🧩 동작 방식 시각화 (간단한 이미지 느낌으로 설명)

 

다음 구조의 그래프가 있다고 가정:

1
├─ 2
│  ├─ 4
│  └─ 5
└─ 3

BFS 탐색 순서는 다음과 같은 형태:

 

1 → 2 → 3 → 4 → 5

 

즉, 1과 가까운 2, 3을 먼저 방문,

그 다음 거리인 4, 5를 방문하는 구조

 

DFS는 깊이로 내려가는 방식

BFS는 레벨(층단)별로 방문하는 방식

 

---

 

⚙ BFS 구현 과정

 

 

1. 탐색 준비

 

• 그래프를 인접 리스트로 초기화
• 방문 배열 생성
• 시작 노드를 큐에 삽입

 

 

2. 큐에서 노드를 하나 꺼내기

 

• 꺼낸 노드를 방문하고
• 해당 노드의 인접 노드 중 방문하지 않은 노드만 큐에 삽입

 

 

3. 큐가 empty 상태가 될 때까지 반복

 

• 큐가 비어있다는 것은 더 이상 탐색할 노드가 없다는 의미
• 방문 배열을 통해 중복 방문을 방지하는 구조

 

---

 

📘 예제: 백준 1260 DFS/BFS 문제

 

문제: https://www.acmicpc.net/problem/1260

 

아래 코드는 DFS와 BFS를 모두 구현한 코드

BFS의 기본 흐름을 이해하기 좋은 형태

package c5_search.bfs;

import java.util.*;

public class P1260_4 {
    static boolean visited[];
    static ArrayList<Integer>[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();
        int start = sc.nextInt();

        // 1. 인접리스트 초기화
        arr = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            arr[i] = new ArrayList<>();
        }

        // 간선 입력
        for(int i = 0; i < e; i++){
            int first = sc.nextInt();
            int last = sc.nextInt();
            arr[first].add(last);
            arr[last].add(first);
        }

        // 방문 배열 초기화
        visited = new boolean[n+1];

        // 번호가 작은 노드부터 방문하기 위한 정렬
        for(int i = 1; i <= n; i++){
            Collections.sort(arr[i]);
        }

        // DFS 출력
        dfs(start);
        System.out.println();

        // BFS 방문 배열 초기화
        visited = new boolean[n+1];

        // BFS 출력
        bfs(start);
    }

    // DFS (재귀 방식)
    public static void dfs(int node){
        System.out.print(node + " ");
        visited[node] = true;

        for(int next : arr[node]){
            if(!visited[next]) dfs(next);
        }
    }

    // BFS (큐 방식)
    public static void bfs(int node){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while(!queue.isEmpty()){
            int now = queue.poll();
            System.out.print(now + " ");

            for(int next : arr[now]){
                if(!visited[next]){
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

 

---

 

📝 BFS에서 꼭 기억해야 할 포인트

 

 

✔ 1. BFS는 큐 기반 구조

 

핵심은 선입선출(FIFO)

먼저 발견된 노드를 먼저 방문하는 방식

 

 

✔ 2. 방문 체크는 노드를 큐에 넣을 때 즉시 처리

 

중복 방문 방지 및 불필요한 삽입 차단

 

 

✔ 3. 그래프는 인접 리스트 사용

 

인접 리스트는 메모리 효율성과 순회 성능 모두 최적

 

 

✔ 4. 정렬(Optional)

 

문제 조건에 따라 “작은 번호 먼저 방문” 요구 시 정렬 필수

 

---

 

💡 BFS는 언제 사용할까?

 

• 그래프에서 최단 거리를 구해야 하는 경우
• 미로 탐색
• 레벨 단위 탐색이 필요한 문제
• 네트워크/연결 관계를 넓게 탐색하는 문제
• 토마토 문제처럼 “전파” 형태의 시뮬레이션

 

DFS와 함께 코딩테스트 탐색 문제에서 기본적으로 요구되는 알고리즘 형태

 

---

 

📌 마무리

 

BFS는 가까운 노드부터 차례로 탐색하는 대표적인 그래프 알고리즘

큐 기반의 구조만 이해하면 구현 난이도가 낮고,

최단 거리·단계별 탐색 문제에서 강력한 효과를 발휘하는 방식

 

DFS와 함께 반드시 익혀야 하는 코딩테스트 기본 탐색 알고리즘

 

---