[알고리즘] BFS

👌 너비 우선 탐색 BFS (Breadth-First Search)

너비를 우선으로 탐색을 수행하는 그래프 알고리즘. 다른 말로는 인접한 노드를 먼저 탐색하는 방법으로, 기본적인 개념은 깊게 탐색하기 전에 넓게 탐색하는 것이다. 최단경로를 찾아주므로 최단 길이를 보장해야 할 때 많이 사용하고, FIFO (First-in First-out) 방식으로 탐색한다.

e.g. 지구상에 존재하는 모든 친구 관계가 그래프 G라고 할때, Jennie와 Rose 사이의 경로를 찾는 경우
->DFS: 모든 친구 관계를 다 살펴봐야 할 가능성
->BFS: Jennie와 가까운 관계부터 탐색

✔ 알고리즘

1. 시작 노드를 큐에 삽입 enqueue
2. 큐에서 하나의 노드를 꺼냄 dequeue
3. 해당 노드에 연결된 노드 중 아직 방문하지 않은 노드를 방문하고 큐에 삽입 enqueue

✔ 시간복잡도

정점의 수가 N, 간선의 수가 E일때 시간복잡도:
->인접 리스트로 표현된 그래프: O(N+E)
->인접 행렬로 표현된 그래프: O(N^2)

👉 관련 문제

• 백준 13549 - 숨바꼭질3

👍 참고 사이트

• [알고리즘] 너비 우선 탐색(BFS)이란