본 글은 DFS에 이어 작성된 글입니다. 먼저 DFS를 읽고 오시는 것을 권장합니다.

 DFS의 단점 중 하나는 항상 최적의 솔루션을 찾는 것이 아니라는 것입니다. BFS는 이런 단점을 보완한 검색 방법입니다. 전반적으로 DFS와 유사하므로 동일한 부분은 생략하고 차이나는 부분 위주로 살펴보겠습니다.

---

Algorithm: BFS Process

 검색 문제는 아래와 같은 과정에 따라 접근합니다.
 1. Frontier는 초기 상태(A)를 포함한 상태, Explored set은 비어있는 상태에서 시작합니다.
 2. 아래 과정들을 반복합니다.
   1) Frontier에 검색할 다음 노드 ^node가 존재하는지 확인합니다. 만약 비어 있다면 솔루션은 없으며 검색 과정을 종료합니다. 참고로 노드란 상태 ^state, 부모 노드 ^{parent node}, 행동 ^action, 비용 ^{path cost}에 대한 정보를 담고 있는 데이터 구조라고 볼 수 있습니다.
    2) 노드 가져오기: Frontier에서 첫 번째 노드를 추출합니다. (queue 구조)
    3) 솔루션 확인과 리턴: 만약 2)의 노드가 목표하는 노드라면 검색과정을 종료하고 솔루션을 리턴합니다.
    4) 노드 추가: Explored set에 노드를 추가합니다.
    5) Frontier 확장: Frontier에 하위 노드(child node)를 추가합니다. 이 때 하위 노드가 frontier와 explored set에 존재하는지 확인합니다. 만약 존재한다면 하위 노드는 추가할 수 없습니다.

 위 과정에서 DFS와 어떤 차이점을 찾아볼 수 있을까요?
 검색 과정에서 DFS는 마지막 노드(F)를 만날 때까지 계속 하위 노드를 찾아갑니다. 하지만 BFS는 우선 같은 깊이의 모든 노드(C, D)를 우선 검색합니다. 매번 검색하는 노드가 목표 노드(E)와 일치하는지 비교한 뒤 일치한다면 검색 과정을 종료합니다.
 이처럼 동일한 깊이의 모든 노드로 확장하며 검색하는 방식이 BFS ^{Breadth First Search}입니다. BFS는 queue 구조를 사용하여 노드를 검색합니다.

 노드의 수를 V ^Vertex, 연결선의 수를 E ^Edge라고 할 때, BFS의 공간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다. 시간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다.

 BFS의 장, 단점은 아래와 같습니다.

 BFS를 미로찾기 문제에 적용해 보겠습니다.

 'QueueFrontier' 클래스는 'StackFrontier' 클래스를 상속 받습니다.
 다만 DFS와 차이점은 'remove' 함수가 frontier에서 노드를 가져올 때 가장 첫 번째 위치에 존재하는 노드를 가져온다는 것입니다. Queue 자료 구조를 사용합니다. 그 외 코드는 DFS와 동일합니다.
 전체 코드와 예제 파일은 이 곳에서 확인할 수 있습니다.

---

Algorithm: BFS Example

 앞서 실제 미로 문제 파일을 DFS로 풀 때, 가까운 솔루션을 두고 멀리 돌아가는 솔루션을 리턴한 케이스가 있었습니다. 이번에는 BFS를 적용해서 풀어보겠습니다.

 BFS의 장점으로 알아봤던 것처럼 최적의 솔루션을 찾아냈습니다.