[JAVA] BFS 너비 우선 탐색

 

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

: 그래프 또는 트리 탐색 알고리즘 중 하나로 너비 우선으로 탐색을 진행한다. BFS는 특정 노드에서 시작해 인접한 노드들을 먼저 탐색한 뒤 그 다음 단계의 노드들을 탐색하는 방식으로 작동한다.

---

 

📍BFS의 특징

• 너비 우선 탐색 : 현재 노드와 인접한 모든 노드를 탐색한 후에 다음 깊이로 진행.
• 최단 경로 보장 : 가중치가 없는 그래프에서 시작 노드와 목표 노드 간의 최단 경로 보장.
• 큐 사용 : 탐색 과정에서 방문할 노드들을 큐에 저장하여 FIFO(First In, First Out) 방식으로 처리.
• 방문 처리 필요 : 이미 방문한 노드를 다시 탐색하지 않도록(무한 루프 방지) 방문 여부를 체크하는 배열 또는 집합 사용.

 

📍BFS의 동작 흐름

1. 초기화 : 시작 노드를 큐에 삽입하고 방문 처리한다.

2. 반복 : 큐에서 노드를 하나 꺼내고, 해당 노드와 인접한 모든 노드 중 방문하지 않은 노드를 큐에 삽입해 방문 처리한다.

3. 종료 : 큐가 비어 있으면 탐색을 종료한다.

 

 

📍BFS 활용 예시

• 최단 경로 탐색 : 코딩테스트에서 자주 볼 수 있는 문제로 최단 경로 보장 가능하므로 DFS가 아닌 BFS를 사용해야 함.
• 그래프 탐색
• 트리 구조 활용
• 네트워크 탐색

 

📍BFS 구현 코드

// BFS 메서드
public static void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()]; // 방문 여부 체크
    Queue<Integer> queue = new LinkedList<>(); // 큐 사용

    // 시작 노드 처리
    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int currentNode = queue.poll(); // 큐에서 노드 꺼내기
        System.out.print(currentNode + " "); // 현재 노드 출력

        // 인접 노드 탐색
        for (int neighbor : graph.get(currentNode)) {
            if (!visited[neighbor]) { // 방문하지 않은 노드만 처리
                queue.add(neighbor);
                visited[neighbor] = true;
            }
        }
    }

 

무방향 그래프 탐색 예제 코드로

시작 노드를 큐에 추가하고 방문 여부를 표시한다.

큐에서 노드를 꺼내 인접한 노드들을 순회하면서, 방문하지 않은 노드는 큐에 추가하고 방문 처리한다.

 

📍BFS vs. DFS

특징	BFS	DFS
탐색 순서	너비 우선 탐색	깊이 우선 탐색
자료 구조	큐(Queue)	스택(Stack) 또는 재귀
최단 경로 보장	가중치 없는 그래프에서 보장	보장하지 않음
메모리 사용량	비교적 더 큼	비교적 더 적음
용도	최단 경로 탐색, 연결 요소 탐색 등	모든 경로 탐색, 백트래킹 문제

 

 

🔗 BFS 관련 백준 문제 풀이

https://aaahyunseo.tistory.com/132

[Baekjoon] 1260 DFS와 BFS - JAVA

https://aaahyunseo.tistory.com/144

[Baekjoon] 2606 바이러스 - JAVA

https://aaahyunseo.tistory.com/149

[Baekjoon] 14940 쉬운 최단거리 - JAVA