너비 우선 탐색(breadth-first-search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
특징으로 Queue 자료구조를 이용하고, 시간 복잡도는 O(V+E) V = 노드 수, E = 엣지 수 이다.
너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기
방문한 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 추가적인 배열이 필요하다.
https://mngprog.tistory.com/39
2178번 (Silver 1)
https://www.acmicpc.net/problem/2178BFS로 푸는 가장 보편적인 문제인 미로에서 최소거리 탐색문제이다. #include #include #include using namespace std;void BFS(vector>&);int main() { cin.tie(0)->sync_with_stdio(false); int N, M; cin
mngprog.tistory.com
위의 백준문제를 풀어보면 BFS를 이해하기 쉽다.
'Algorithm' 카테고리의 다른 글
| 4-1 탐색(DFS) (0) | 2025.01.20 |
|---|---|
| 3-3 정렬(RadixSort) (0) | 2025.01.20 |
| 3-2 정렬(Merge Sort) (0) | 2025.01.19 |
| 3-1 정렬(Quick Sort) (0) | 2025.01.18 |
| 2.투 포인터 (0) | 2025.01.18 |