루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

• 맹목적인 탐색을 하고자 할 때 사용할 수 있다.
• 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 큐 - Queue 자료구조를 이용해 구현한다.

동작 원리

BFS의 동작은 큐를 이용해 지금 위치에서 갈 수 있는 노드를 모두 넣는 방식으로, 큐에 넣는 동시에 방문했다고 체크해야 한다.

준비물

• 그래프 혹은 트리
• Queue
• 방문여부 확인용 배열

  트리가 아닌 그래프에 꼭 필요하다.

BFS를 통해 해결할 수 있는 문제의 조건

1. 최소 비용 문제이어야 한다.
2. 간선의 가중치가 1 이어야 한다.
3. 정점과 간선의 개수가 적어야 한다.