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

BFS(Breadth-First Search)

bfs란 그래프에서 가까운 곳부터 넓게 탐색하는 알고리즘고리즘이다.
✔ 큐(Queue) 사용
 https://velog.io/@seha01130/DFSDepth-First-Search-깊이우선탐색
✔ 최단 거리 찾기에서 자주 쓰임

탐색순서

간선: (1-2), (1-3), (2-4), (3-5)
시작 노드: 1

     1
    / \   
   2   3
  /     \
 4       5
 
 이런 그래프가 존재할 때 bfs 탐색 순서는 1 → 2 → 3 → 4 → 5 가 된다

1을 큐에 enqueue [1]
1을 dequeue하면서 연결된 2, 3을 큐에 enqueue하고 차례대로 꺼냄 [2, 3]
먼저 2 dequeue하면서 → 4 enqueue [3, 4]
그다음 3 dequeue → 5 enqueue [4, 5]
그 다음 4 dequeue [5]
그 다음 5 dequeue []

bfs는 명시적으로 Queue를 쓴다

BFS는 반복문으로 돌려야 하므로 명시적으로 Queue를 써야 함.

예를 들어 아래의 코드를 보자. 아래의 코드는 백준 2606번: 바이러스 라는 문제를 푼 풀이이다.
bfs방식을 사용하여 풀었다.

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); //컴퓨터 수
        int m = Integer.parseInt(br.readLine()); //연결된 쌍의 수

        ArrayList<Integer>[] graph = new ArrayList[n+1];
        for (int i = 1; i <= n; i++){
            graph[i]  = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }
        // ----------------- 간선 정보 입력 완료

        // 방문여부 체크
        boolean[] visited = new boolean[n+1];

        int count = bfs(1, graph, visited);
        sb.append(count);
        System.out.println(sb);
    }

    static int bfs(int node, ArrayList<Integer>[] graph, boolean[] visited){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);
        visited[node] = true; //넣을때 true로 해주는게 맞음. 그래야 중복으로 enqueue하지 않음.
        int count = 0;

        while (!queue.isEmpty()){
            int removed = queue.poll();

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

분명 bfs는 queue를 사용한다고 했는데 위의 코드에서는 ArrayList를 사용하여 정보들을 저장하고있다.
ArrayList<Integer>[] graph = new ArrayList[n + 1];
이건 탐색용 queue가 아니라, 노드들 간 연결 상태(=간선 정보)를 저장하기 위한 자료구조이다.
즉, 탐색을 위한 도구가 아니라 탐색 대상인 지도 같은 역할이다.

Queue는 bfs(...) 함수를 보면 그 내부에서 탐색을 위해 쓰이고 있다.