BFS

BFS(너비 우선 탐색) 란?

너비 우선 탐색(Breadth-First Search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 너비 우선 탐색을 적용합니다.

BFS 방식

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남깁니다.
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행합니다.
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 push합니다.
4. 큐가 빌 때까지 2번을 반복합니다.

이러한 방식의 탐색은 모든 칸이 큐에 1번씩 들어가므로 칸이 N개일 때 시간복잡도는 O(N)입니다.

활용 문제

백준 1926번 https://Geniemo.github.io/boj/1926/

백준 2178번 https://Geniemo.github.io/boj/2178/

백준 7576번 https://Geniemo.github.io/boj/7576/

백준 4179번 https://Geniemo.github.io/boj/4179/

백준 1697번 https://Geniemo.github.io/boj/1697/