너비우선탐색
-
[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)Algorithm 2020. 12. 11. 19:13
너비 우선 탐색 (BFS, Breadth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 너비 우선 탐색은 현재 위치를 기준으로 사방으로 퍼져나가면서 탐색하는 방법으로, 인접한 정점들을 먼저 탐색한 후에 차례로 탐색을 진행한다. 장점 모든 가중치가 동일할 때, 시작 정점으로 부터 목표까지 최단 경로를 보장한다. 단점 정점의 수가 늘어날 수록 탐색에 불필요한 정점을 저장해야 하기 때문에 저장공간이 비교적 많이 필요하다. 주로 두 정점 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다. 점점 탐색 범위를 확장하며 탐색하기 때문에 처음 발견하는 경로가 최단 경로가 된다. 주의할 점은 DFS와 마찬가지로 방문 체크가 필요하다. 그림으로 이해하면 쉽기 ..