BFS(Breadth-First Search) 너비 우선 탐색

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리에서 시작 노드로부터 가까운 노드부터 탐색하는 알고리즘

✅ 핵심 개념

• 가까운 노드부터 탐색
• Queue(큐) 자료구조 사용
• 최단 거리 탐색에 적합
• 그래프의 레벨 순서 탐색 가능

📌 예시로 이해하기

     1
   /   \
  2     3
 / \     \
4   5     6

✅ BFS 동작 과정 (요약)

1. 시작 노드를 큐에 삽입하고 방문 표시
2. 큐에서 노드를 꺼내서 인접한 노드들을 모두 큐에 추가
3. 추가할 때 방문하지 않은 노드만 추가
4. 큐가 빌 때까지 2~3 반복

✅ Java 코드

import java.util.*;

public class BFSExample {
    public static void main(String[] args) {
        // 인접 리스트로 그래프 표현
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4, 5));
        graph.put(3, Arrays.asList(6));
        graph.put(4, new ArrayList<>());
        graph.put(5, new ArrayList<>());
        graph.put(6, new ArrayList<>());

        bfs(graph, 1);
    }

    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(start);
        visited.add(start);

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

            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
}