너비우선탐색은 백트랙을 하지 않는다. 대신에 현재 정점에서 깊이가 1인 정점을 모두 방문해야 하므로 큐(queue)라는 선입선출(FIFO) 자료구조를 활용하여 현재 정점에서 깊이 가 1 더 깊은 모든 정점을 순차적으로 큐에 저장하여
탐색에 활용한다.
알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘
BFS 너비 우선 탐색 탐색을 할때 너비를 우선으로 탐색하는 알고리즘 BFS 탐색 알고리즘을 통해 '최단 경로'를 찾을 수 있다. 응용하면 미로찾기와 같은 알고리즘도 구현할 수 있다. BFS를 구현하기
hongku.tistory.com
'Algorithm > Etc' 카테고리의 다른 글
| 오른편 절단 가능 소수 (0) | 2020.08.10 |
|---|---|
| 최대값 구하기 (0) | 2020.08.04 |
| [C++ / STL] sort (0) | 2020.08.03 |
| 백트랙 (0) | 2020.08.03 |
| Graph and Tree (0) | 2020.07.31 |
