[알고리즘] BFS(Breadth-First Search)이란 ?

📁너비 우선 탐색(BFS)

트리나 그래프를 탐색하는 기법 중 하나로, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 깊게 탐색하기 전에 넓게 탐색하는 것이다.

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 미로 찾기 등 최단 거리를 구해야 할 경우 사용된다.

1️⃣ 너비 우선 탐색 과정

1. 시작 노드에 방문한다. (무한 루프를 돌지 않기 위해 방문 여부 체크 필수)
   1-1. 큐에 방문된 노드를 삽입(enqueue)한다.
   1-2. 초기 상태의 큐에는 시작 노드만이 저장된다.
2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
   2-1. 큐에서 꺼낸 노드를 방문한다.
   2-2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
   - 인접한 노드가 없다면 모두 탐색을 완료했으므로 큐에서 노드를 제거(dequeue)한다.
   2-3. 큐에 방문된 노드를 삽입(enqueue)한다.
3. 큐가 소진될 때까지 반복한다.

2️⃣ 너비 우선 탐색의 구현

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

        bfs(1);
        System.out.println(sb);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()+1];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node).append(" ");

            List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
            for(int neighbor : neighbors) {
                if(!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

• 초기 상태
  graph HashMap은 각 노드와 연결된 노드들을 나타낸다.
  visited 배열은 각 노드의 방문 여부를 추적하며 초기에는 모든 값이 false이다.
  현재 큐의 값 : 1
• bfs(1) 호출 시
  노드 1을 방문하고 queue에서 값을 제거한다.
  visited[1] = true로 방문 표시
  StringBuilder의 현재 값 : 1
  노드 1과 연결된 노드들(2,3)을 큐에 넣는다.
  현재 큐의 값 : 2, 3
• bfs(2) 호출 시
  노드 2를 방문하고 queue에서 값을 제거한다.
  visited[2] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2
  노드 2과 연결된 노드들(4,5)을 큐에 넣는다.
  현재 큐의 값 : 3, 4, 5
• bfs(3) 호출
  노드 3을 방문하고 queue에서 값을 제거한다.
  visited[3] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2 3
  노드 4과 연결된 노드들(6,7)을 큐에 넣는다.
  현재 큐의 값 : 4, 5, 6, 7
• bfs(4) 호출
  노드 4를 방문하고 queue에서 값을 제거한다.
  visited[4] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2 3 4
  노드 4는 자식 노드가 없으므로, 다음 큐에서 꺼낼 노드인 5으로 이동한다.
  현재 큐의 값 : 5, 6, 7
• bfs(5) 호출
  노드 5를 방문하고 queue에서 제거한다.
  visited[5] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2 3 4 5
  노드 5는 자식 노드가 없으므로, 다음 큐에서 꺼낼 노드인 6으로 이동한다.
  현재 큐의 값 : 6, 7
• bfs(6) 호출
  노드 6를 방문하고 queue에서 제거한다.
  visited[6] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2 3 4 5 6
  노드 6는 자식 노드가 없으므로, 다음 큐에서 꺼낼 노드인 7으로 이동한다.
  현재 큐의 값 : 7
• bfs(7) 호출
  노드 7를 방문하고 queue에서 제거한다.
  visited[7] = true로 방문 표시
  StringBuilder의 현재 값 : 1 2 3 4 5 6 7
  노드 7는 자식 노드가 없고, 다음 큐 값이 존재하지 않으므로 반복을 종료한다.
  현재 큐의 값 :
• 반복 종료
  모든 인접한 노드를 방문했으므로 반복을 종료한다.
  

3️⃣ BFS 정리

장점

1. 최단 경로를 보장하며, 트리의 레벨 순으로 탐색이 가능하다.
2. 구현이 비교적 간단하며, 이해하기 쉽다.
3. 모든 노드를 방문 할 수 있다.

단점

1. 큐 사용으로 인해 많은 정점이 저장되면 메모리를 많이 소모할 수 있다.
2. 그래프가 넓거나 간선이 많은 경우 비효율적일 수 있다.

4️⃣ 시간복잡도

(노드 수 : N, 엣지 수 : E)

인접 리스트

• 노드의 개수가 많고, 간선의 수가 적을 때 유리

인접 행렬

• 노드의 개수가 적고, 간선의 수가 많을 때 유리