[알고리즘] BFS(넓이 우선 탐색)

BFS(Breadth-First Search)란?

BFS란 넓이 우선 탐색이란 뜻으로 그래프 탐색의 일종이다. 흔히들 그래프 탐색이라 하면 DFS와 BFS 두개가 있는데 DFS와 다른 점은 다음에 방문할 노드를 정할때 주변에 있는 노드가 우선이라는 점이다. 보통 그래프에서 최단 경로를 찾을때 가장 많이 사용된다.

BFS의 특징

• BFS는 스택의 구조를 가지는 DFS와 달리 FIFO 탐색으로 구현된다.
• 위와 같은 이유로 사용되는 자료구조 역시 stack이 아닌 queue를 사용한다.
• 시간 복잡도는 DFS와 같은 O(V+E)를 가진다.
• 재귀적으로 동작하지 않는다. 즉 검색 속도에 있어서 이점을 가질수 있다.

BFS의 원리

1. BFS 시작 노드 정하고 자료구조 초기화
   • BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않기 때문에 방문 여부를 저장할 배열을 초기화한다.
   • 역시 마찬가지로 그래프를 구현하기위해 인접 리스트를 사용한다.
   • DFS와 다른 점으로 방문할 노드를 저장할 곳을 스택이 아닌 큐로 구현한다.
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드를 다시 큐에 넣기
   • 큐에서 노드를 꺼내고 그래프를 이용하여 해당 노드의 인접 노드를 찾는다.
   • 이때 꺼낸 노드는 탐색 순서에 기록을 한다.
   • 인접 노드를 찾으면 해당 노드들의 방문 여부를 확인하고 방문하지 않은 노드만 큐에 넣는다.
3. 큐에 노드가 없을 때 까지 반복
   • 1번과 2번 과정을 모든 노드에 방문할 때까지 반복을 하면 BFS를 완료한다.
   • 단 여기서 조심할 점은 LIFO인 DFS와 달리 FIFO인 BFS에서 탐색 순서가 달라지는 것을 유의한다
   • 최종적으로 모두 완료하면 탐색 순서가 나오게 되는데 이것이 모든 노드를 방문하는 최소 거리가 된다.
   • 만약 여기서 간선에 가중치가 붙으면 또 동작이 추가된다.