Day-8 너비 우선 탐색 BFS

---

1. 너비 우선 탐색

• BFS(breadth-first search)는 그래프 완전 탐색 기법 중 하나이다.
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색한다.
• FIFO 탐색이며 큐를 이용한다.
• 시간 복잡도는 O(노드 수 + 엣지 수)이다.
• 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

---

2. 너비 우선 탐색 과정

BFS를 사용하려면 인접 리스트, 방문 체크 배열, 큐가 필요하다.

큐에서 노드를 꺼내고 꺼낸 노드의 인접 노드를 다시 큐에 넣는다.

방문한 노드이면 큐에 넣지 않는다.

 

위와 같은 과정을 큐가 빌 때까지 반복한다.

---

3. 예제 문제

[1260] DFS와 BFS (JAVA)

---

[2606] 바이러스 (JAVA)