[Algorithm] BFS - 넓이 우선 탐색

목표

---

• 알고리즘 문제를 풀면서 DFS를 정리한 글로 정리한 적이 있다. BFS 또한, 완벽하게 알고있어야하는 알고리즘이라고 판단되어 DFS와 반대되는 탐색 개념인 BFS 그래프 탐색 알고리즘에 대해 이해하고 하고자 한다. DFS의 개념이 부족하다면 아래 글을 읽고 오면 좋다.

https://zzzzseong.tistory.com/23

[Algorithm] DFS - 깊이 우선 탐색

 

 

BFS(Breadth First Search)란

---

BFS(Breadth First Search)

• BFS란 초기 노드에서 시작하여 깊이를 하나씩 들려가며 해당 레벨의 모든 자식노드를 탐색하여 해를 찾는 완전탐색 알고리즘이다. BFS는 깊이를 하나씩 들려가며 해를 찾는 방식이기때문에 항상 최적해를 보장한다.
• BFS는 재귀를 이용해 구현하는 DFS와 달리 Queue와 반복문을 이용해 구현하는것이 일반적이다. 아래 트리를 이용해 BFS 알고리즘을 이해해보도록 하자.

 

• BFS 알고리즘의 탐색 방향은 Queue에 저장된 노드의 순서대로 탐색을 진행한다. 해당 예시에서는 왼쪽 자식노드가 오른쪽 자식노드보다 앞에 있다고 가정한다. 초기노드 1에서 시작해 5의 값을 가지는 목표노드를 찾아보자.

 

• Queue에서 미리 넣어놓은 초기노드인 1번 노드를 가져온 다음 1번 노드가 목표노드가 아니라면 1번 노드의 자식노드를 차례대로 Queue에 삽입한다.

 

• Queue에서 가장 앞에있는 2번 노드를 가져온 다음 2번 노드가 목표노드가 아니라면 2번 노드의 자식노드를 차례대로 Queue에 삽입한다.

 

• 다음으로, Queue에서 가장 앞에있는 3번 노드를 가져온 다음 3번 노드가 목표노드가 아니라면 3번 노드의 자식노드를 차례대로 Queue에 삽입한다.

 

• DFS에서는 깊이 방향으로 탐색하고, 더이상 진행 불가하다면 백트래킹을 이용해 돌아가서 다른 자식을 탐색하는 과정을 거치지만, BFS는 사실 지금까지 해온 것을 목표 노드를 찾을때까지 계속해서 반복하면 되는 매우 단순한 알고리즘이다.
• 이후로의 과정은 지금까지의 과정을 반복하는 것이기 때문에 설명은 생략하고 목표노드를 찾을때까지 그림으로만 과정을 설명하겠다.

 

 

 

 

BFS(Breadth First Search) Code

---

• 앞서 BFS 알고리즘의 탐색방식을 살펴본 것처럼 BFS는 단순하기 때문에 그 쓰임 또한 명확하다고 생각한다. 아래는 본인이 생각한 BFS를 가장 기본적으로 구현한 코드이며 더 높은 수준의 문제를 해결하기 위해서는 다른 방법 또는 조건이 필요할 수 있다.

package Algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class bfs {
    //노드 데이터를 저장하기 위한 자료구조 선언
    private List<List<Integer>> graph = new ArrayList<>();

    //BFS를 위한 자료구조 선언
    private Queue<Integer> queue = new LinkedList<>();

    //목표노드 5 선언
    private int answer = 5;

    public void bfs() {
        //초기 노드 삽입
        queue.offer(1);

        //queue가 비어있을때까지 즉, 모든 노드를 탐색할때까지 반복
        while(!queue.isEmpty()) {

            //가장 앞에 들어있는 노드 추출
            Integer curNode = queue.poll();

            //목표노드에 도달했다면 종료
            if(curNode == answer) break;

            //목표노드에 도달하지 못했다면 자식노드 삽입
            for (Integer nextNode : graph.get(curNode)) {
                queue.offer(nextNode);
            }
        }
    }
}