[알고리즘] BFS (Breadth-First-Search)

1. BFS란?

BFS는 Breadth-First-Search의 줄임말로, 한국어로는 너비 우선 탐색이라고 한다. BFS에 대해 알기 위해서는 먼저 그래프 탐색에 대해 알아야 한다.

• 그래프 탐색이란?

  하나의 정점에서 탐색을 시작하여 차례대로 모든 정점을 방문하는 것이다. 그래프들의 데이터들은 정렬되어있지 않기 때문에 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 한다.

결론적으로 BFS란 루트 노드에서 시작하여 인접한 노드들을 먼저 탐색하는 방법이다. 시작 정점에서부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점들을 나중에 방문하는 순회 방법인 것이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 방법인 것이다. 그래서 넓이 우선 탐색이라 일컫는다.

2. BFS의 특징

• 두 노드 사이의 최단 거리나 임의의 경로를 찾고 싶을 때 주로 사용할 수 있다.
  • 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프에서 최단 경로를 알아낼 수 있다. (가중치가 있는 그래프는 Dijkstra 알고리즘을 이용)
• 자료구조 큐(queue)를 사용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서로 탐색한다.

3. BFS의 구현 과정

1) 그래프에서의 BFS

1. 시작 노드에 방문한다.
   • 큐에 방문한 노드를 push한다.
   • 초기 상태의 큐에는 시작 노드만 저장된다.
2. 큐의 가장 앞 노드를 확인하고 인접한 노드들을 모두 차례로 방문한다.
   • 큐의 가장 앞 노드에 방문한다.
   • 해당 노드와 인접한 노드들을 모두 방문한다.
     • 해당 노드의 자식 노드들을 모두 큐에 저장하는 것과 같다.
     • 인접한 노드가 없다면 해당 노드를 pop한다.
3. 큐에 남은 노드가 없을 때까지 반복한다.
   • 모든 노드를 방문하면 탐색을 마친다.

2) 다차원 배열에서의 BFS

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
2. 큐의 가장 앞 노드를 확인하고 해당 칸의 상하좌우로 인접한 칸에 대해 3번 과정을 실행한다.
3. 해당 칸을 이전에 방문한 적이 있으면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남긴 뒤 해당 칸을 큐에 push한다.
4. 큐에 아무것도 남지 않을 때까지 2-3번 과정을 반복한다.