너비 우선 탐색 알고리즘이란?

오늘은 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색에 대해 알아보려고 한다

먼저 너비 우선 탐색은 이름에서 알 수 있듯이 시작 정점에서 인접한 정점들을 먼저 탐색하며 이후 더 이상 방문할 수 있는 곳이 없으면 다음 정점으로 너비 탐색을 진행하는 방식의 알고리즘이기 때문에 너비 우선 탐색이라고 붙여졌다

너비 우선 탐색이란?

너비 우선 탐색(BFS, Breadth First Search)은 그래프의 모든 정점을 방문하는 방식 중 하나로 그래프에서 한 노드의 인접한 모든 정점들을 먼저 탐색하며 더 이상 방문할 노드가 없을 때 다음 레벨의 노드로 이동하여 탐색을 계속하는 방식으로

일반적으로 큐 자료구조를 사용하여 구현하며 그래프의 모든 정점을 방문하게 된다

너비 우선 탐색의 작동 방식

이러한 너비 우선 탐색은 다음과 같은 방식으로 작동한다

1. 시작 노드를 큐에 넣고 방문 처리를 한다
2. 큐의 맨 앞 노드를 꺼내어 그 노드의 방문하지 않은 인접 노드를 모두 큐에 넣고 방문 처리한다
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 그래프에서 A라는 정점에서 시작하여 깊이 우선 탐색을 진행한다고 했을 때

그래프:

    A
   / \
  B   C
 /     \
D       E
         \
          F

진행 순서:

A -> B -> C -> D -> E -> F

와 같은 순서로 노드를 방문하게 된다

너비 우선 탐색의 장단점

마지막으로 깊이 우선 탐색 알고리즘의 장단점을 알아보자

장점:

1. 두 노드 사이의 최단 경로나 임의의 경로를 찾을 때 사용할 수 있다
2. 모든 정점을 방문하게 된다

단점:

1. 경로가 매우 길 경우에는 많은 기억 공간이 필요하다
2. 모든 간선을 검사해야 하므로 시간이 오래 걸릴 수 있다