BFS:Breadth-First Search 너비 우선 탐색

BFS :Breadth-First Search:  너비 우선 탐색이며 너비를 우선적으로 탐색

 

2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며

주변을 순차적으로 방문하여 모든 노드를 탐색하는 방법

 

모든 노드를 탐색하는 알고리즘으로 깊이 우선 탐색을 하는 DFS와는 달리

Stack을 이용하지 않으며

Queue를 이용하여 전개한다.

• DFS - 재귀, stack 자료 구조 활용
• BFS - Queue 자료 구조 활용

 

Point: 

1. 탐색할 2차원 배열 또는 그래프

2. 방문처리를 하기 위한 boolean type  =>변수명: visited

3. Queue 자료 구조