알고리즘
탐색(2) - BFS
조앤박
2023. 9. 17. 03:35
너비 우선 탐색
너비 우선 탐색(BFS, breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.
| 기능 | 특징 | 시간복잡도(노드 수 : V, 엣지 수 : E) |
|---|---|---|
| 그래프 완전 탐색 | - FIFO 탐색 - Queue 자료구조 이용 | O(V+E) |
너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러개일 때 최단 경로를 보장합니다.
너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요합니다. 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일합니다. 하지만 차이점이 있다면 탐색을 위해 스택이 아닌 큐를 사용합니다.
- 타임라인 : 원본 그래프 -> 인접 리스트 -> 방문 배열 -> 큐 삽입
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입합니다. 이 때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않습니다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록합니다.
- 타임라인 : 큐에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드를 기록 -> 인접 리스트 -> ㄷ상 노드의 인접 노드를 큐에 삽입 -> 노드를 삽입하며 방문 배열 체크
3. 큐 자료구조에 값이 없을때까지 반복하기
큐에 노드가 없을 때까지 앞선 과정을 반복합니다. 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와는 다릅니다.
풀어볼 문제