BFS
그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용
* DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다.
Process
※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서는 발견과 방문이 같지 않습니다.
① 아직 발견되지 않은 상태
② 발견되었지만 아직 방문되지 않은 상태 (큐에 저장되어 있는 상태)
③ 방문된 상태
DFS와 BFS 비교
출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노드로 가는 경로들 모..
zoosso.tistory.com
활용
최단 경로를 찾을 때 유용
※ BFS와 달리 DFS는 그래프의 구조에 관련된 다양한 문제를 푸는 데 사용됨
그래프 전체의 구조에 관한 정보를 얻기 위해 사용되는 깊이 우선 탐색과 달리
너비 우선 탐색은 대개 시작점으로부터 다른 정점들까지의 거리를 구하기 위해 사용됩니다.
따라서 DFS 처럼 모든 정점을 검사하는 작업은 잘하지 않습니다.
큐 설정 (STL 사용하지 않을 시)
- 가중치 등으로 중복 방문을 허용하지 않는 경우는
visited[][] 배열 크기만큼 처리할 수도 있습니다.
- 중복 방문이 허용되지 않는 경우
상하좌우는 10배, , 이지만 그렇지 않은 문제는 50배, 100배가 필요한 경우도 있음
우선순위 큐로 구현하는 경우에는 중복방문을 허용하더라도,
배열 크기만큼 처리해도 대부분 문제가 풀림
관련 문제
- [SWEA] 9236 곰돌이 (BFS + 이분탐색, Upper Bound)
'알고리즘' 카테고리의 다른 글
| 정방행렬 90° 회전 (python) (0) | 2021.02.28 |
|---|---|
| PS시 자주 사용하는 함수 모음 (0) | 2021.02.28 |
| 깊이 우선 탐색(depth-first search, DFS) (0) | 2021.02.27 |
| 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) (0) | 2021.02.27 |
| Disjoint-Set & Union-Find (0) | 2021.02.27 |
댓글