너비우선탐색 BFS (JAVA)

📍 BFS란?

: Breadth-First Search(너비우선탐색)으로,
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다.
-> 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.

1. BFS vs DFS

(1) 깊이 우선 탐색 DFS

• 노드 간의 "하나 하나" 모든 관계를 알아야 할 때 사용한다.
• 재귀적인 특성을 가진다.

(2) 너비 우선 탐색 BFS

• 노드의 최단 경로를 찾을 때 사용한다.
• 깊이 관련 특성을 가진다.
• 재귀적인 특성을 가지고 있지 않다.
• 선입선출(FIFO) 원칙으로 탐색 -> 큐 사용

2. BFS 해결 방식

대부분 큐(Queue)를 사용하여 해결한다.

시작 노드를 큐에 삽입
큐에서 노드를 꺼내서 처리
방문한 노드를 기록
큐가 빌 때까지 위의 과정을 반복

출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

3. 시간복잡도

• BFS의 시간 복잡도 : O(V + E)

노드 수(V): 그래프에 있는 노드(정점)의 수
간선 수(E): 그래프에 있는 간선(엣지)의 수

4. 구현 - 인접 리스트 (JAVA)

자바 코드

import java.util.*;

class Main {
	static boolean[] visited;
    static List<List<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) {
        int n = 6; // 노드 개수
        visited = new boolean[n + 1]; // 방문 배열
        
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 연결 (무방향 그래프)
        graph.get(0).addAll(Arrays.asList(1, 2));
        graph.get(1).addAll(Arrays.asList(0, 3, 4));
        graph.get(2).addAll(Arrays.asList(0, 5));
        graph.get(3).add(1);
        graph.get(4).add(1);
        graph.get(5).add(2);

        System.out.println("BFS 탐색 순서:");
        BFS(0); // 1번 노드에서 시작
    }
    
     public static void BFS (int start) {
        Queue<Integer> queue = new LinkedList<>();
        
        // 시작 노드를 큐에 추가하고 방문 표시
        queue.offer(start);
        visited[start] = true;

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

            // 현재 노드의 인접 노드들을 확인
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) { // 방문하지 않은 노드만 추가
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

출력

BFS 탐색 순서 : 
0 1 2 3 4 5

그래프 구조

                 0
               /  \
             1     2
            /\      \  
           3  4      5

BFS 탐색 과정

0 번 node에서 시작 -> queue = [0]
0 을 꺼내고 1, 2 방문 -> queue = [1, 2]
1 을 꺼내고 3, 4 방문 -> queue = [2, 3, 4]
2 을 꺼내고 5 방문 -> queue = [3, 4, 5]
3 을 꺼내고 더 방문할 node 없음 -> queue = [4, 5]
4 를 꺼내고 더 방문할 node 없음 -> queue = [5]
5 를 꺼내고 더 방문할 node 없음 -> queue = [] 끝