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

"꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고

멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.

시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.

이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다.

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS의 특징

• BFS는 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1부터 2, 3 순서대로)
  ( 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)
• BFS는 재귀적으로 동작하지 않는다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 즉, 선입선출(FIFO) 원칙으로 탐색
• 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

BFS의 수행 과정

BFS 구현 방법

큐(Queue)를 이용

BFS 시간복잡도

• 정점의 수가 n이고, 간선의 수가 e인 그래프의 경우

• 그래프가 인접 리스트로 표현된 경우 O(n+e)
  인접 행렬로 표현된 경우 O(n^2)이다.
  희소 그래프인 경우 인접 리스트의 사용이 인접 행렬보다 유리

• (희소 그래프는 그래프 내에 적은 수의 간선을 가지는 그래프로 인접 행렬을 사용하면 메모리의 낭비가 크기 때문)

연습문제

• 백준 1260번 : DFS와 BFS
• 백준 2178번 : 미로찾기