너비 우선 탐색 (BFS)
- Breadth First Search
- 너비 우선 탐색
- Queue가 사용됨
- 다차원 배열에서 각 칸 방문 시, 너비를 우선하는 알고리즘
- 그래프에서 모든 노드를 방문하기위한 알고리즘에서 나옴.
- 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
장점
- 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작이 가능하다.
- 단순 검색 속도가 DFS보다 빠르다
- 너비 우선 탐색이기에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다.
- 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단 경로를 반드시 찾을 수 있다.
단점
- 재귀 호출의 DFS와 달리 Queue에 다음에 탐색할 정점들을 저장해야 함으로 저장공간이 많이 필요하다. (공간 효율이 좋지 않다.)
- 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기에 비현실적이다.
BFS를 개념적으로 보기보다 문제로 많이 접하는게 더 이해가 편한 것같다.
여러 문제들을 보면서 이해하자.
developer
bfs