너비 우선 탐색/BFS 알고리즘이란?

BFS 알고리즘이란?

BFS는 Breadth-First Search의 약자로 너비 우선 탐색이라고도 불린다.

BFS는 시작노드에서 가까운 노드를 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 탐색 방법이다.

즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

BFS의 특징

• 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때 사용한다.(ex.미로를 빠져나가는 최단경로)
• BFS는 재귀적으로 동작하지 않는다.
• 탐색 시 노드를 방문하면 반드시 방문여부를 체크해야 한다.(이를 검사하지 않으면 무한루프에 빠질 수 있음)
• BFS는 일반적으로 방문한 노드들을 순서대로 저장 후 순서대로 꺼낼 수 있는 자료구조인 큐(Quque)를 사용한다.
  - 즉, 선입선출(FIFO /First in First Out) 원칙으로 탐색한다.

BFS의 과정

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

 

깊이가 아닌 너비를 우선적으로 탐색했기 때문에 0 - 1 - 2 - 4 - 3라는 경로로 탐색하는 것을 볼 수 있다.

 

BFS장점

1. 너비를 우선으로 탐색하기 때문에 여러 경로 중 최단 경로 찾는것을 보장한다.
2. 어느 한 경로가 무한히 깊어져도 최단 경로를 찾을 수 있다.
3. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.

BFS단점

1. 재귀호출과 스택을 사용하는 DFS와 달리 큐를 사용해 다음 탐색할 노드들을 저장하기 때문에 노드의 수가 많을 수록 메모리를 많이 차지하게 된다.
2. 최소 실행시간보다는 오래 걸린다

기초예제

https://www.acmicpc.net/problem/2606

2606번: 바이러스

DFS 포스팅과  같은 예제를 BFS를 사용해서 풀었다 .

DFS의 경우, 재귀함수를 사용했고, BFS는 Queue를 사용했다.

public class Main {
    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Node = Integer.parseInt(br.readLine());
        int Line = Integer.parseInt(br.readLine());
        int[][] arr = new int[Node+1][Node+1];
        int count = 0;

        //간선 입력
        for(int i=1; i<=Line; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a][b] = arr[b][a] = 1;
        }

        boolean[] visited = new boolean[Node+1];

        //BFS 사용을 위한 queue
        Queue<Integer> queue = new LinkedList<Integer>();
        visited[1] = true;
        queue.offer(1);

        //queue에 초기 노드인 1을 넣고, queue가 공백일 될 때까지 반복
        while(!queue.isEmpty()) {
            int start = queue.poll();
            //queue에서 꺼내온 노드가 간선이 있는지 순회하면서 탐색
            for(int i=1; i<=Node; i++) {
                //간선으로 연결된 노드가 있고, 연결된 노드에 방문기록이 없다면 queue에 넣어줌
                if(arr[start][i]==1 && visited[i]!=true) {
                    count++;
                    visited[i] = true;
                    queue.offer(i);
                }
            }//end for
        }//end while
        System.out.println(count);
        
    }//end main
}//end class

---

참고자료

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

https://heytech.tistory.com/56

https://velog.io/@vagabondms/DFS-vs-BFS