04. 넓이 우선 탐색 (BFS)

1. 알고리즘 정의

Breadth-First Search

그래프나 트리에서 Root 노드부터 출발하여

인접한 노드들을 먼저 탐색하고, 그 다음 단계의 노드들을 탐색해 나가는 방식

최단거리 문제에 특히 적합, 주로 Queue를 활용하여 구현함. 

 

[구조]

A
├── B
│   └── D
└── C

BFS 탐색 순서 (시작: A)
→ A → B → C → D

 

2.알고리즘 구현

import java.util.*;

public class BFSExample {
    static List<Integer>[] graph;
    static boolean[] visited;

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

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

            for (int next : graph[current]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();

        // 양방향 그래프 (예시)
        graph[1].add(2);
        graph[1].add(3);
        graph[2].add(4);
        graph[3].add(5);
        graph[2].add(1);
        graph[3].add(1);
        graph[4].add(2);
        graph[5].add(3);

        bfs(1); // 출력: 1 2 3 4 5
    }
}

 

3. 활용 예시

📏 최단 거리 탐색	미로, 지하철 역 간 거리, 네트워크 hop 수 등
🌳 트리의 레벨 탐색	트리에서 depth별로 탐색
🔥 불 퍼지기 문제	주변으로 동시에 번지는 현상 시뮬레이션
🌊 물이 차오르는 시뮬	시간이 지남에 따라 확산되는 패턴
🧬 바이러스 확산, 전염병 시뮬레이션	레벨 기반 전파
📞 친구 추천 알고리즘	소셜 그래프에서 몇 단계 떨어진 친구 추천

 

*) BFS vs DFS 차이점