너비 우선 탐색(BFS)

오늘은 너비 우선 탐색(BFS, Breadth-First Search)에 대해 간략하게 정리해보려 합니다¹. 우선 시작하기 앞서 그래프에 대해서 알아야 하는데요. 알고리즘에서 말하는 그래프는 중고등학교 때 수학시간에 배운 x축, y축과 전혀 관련이 없는 것이더라구요.

 

그래프

알고리즘에서 말하는 그래프는 정점(node)와 간선(edge)를 말합니다.

그래프에 대해 알아야할 것은 여기까지 입니다. 이제는 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 다음과 같은 질문을 해결해줍니다.

• 정점A에서 정점B로 가는 경로가 존재하는가?
• 정점A에서 정점B로 가는 최단 경로는 무엇인가?

특히 두번째 질문 '정점A에서 정점B로 가는 최단 경로는 무엇인가' 를 해결해주는 알고리즘으로 유명하죠. 그럼 이제 너비 우선 탐색이 어떤식으로 구현되는지 알아보겠습니다. 자료구조로는 큐(Queue)를 사용하는데요. 이에 대한 설명은 생략하겠습니다.

 

알고리즘의 구현

1. 맨 처음 시작하는 사람과 이웃하는 사람(간선으로 연결된 사람)을 큐에 넣는다

2. 큐에서 한 사람을 꺼낸다

3. 이 사람이 우리가 찾고자 하는 사람인지 확인한다

   3-1. 우리가 찾고자 하는 사람이 맞으면 작업 완료!

   3-2. 찾고자 하는 사람이 아니면 그 사람의 이웃을 다시 큐에 추가

4. 2~3 작업을 반복!

5. 만약 큐가 비워있으면 모든 사람 중 우리가 찾고자 하는 사람은 없다

 

위의 알고리즘은 다음과 같은 경우에 종류가 됩니다.

• 우리가 원하는 사람을 찾거나
• 큐가 비워지는 경(우리가 원하는 사람이 없는 경우)

 

하지만 이런 경우와 관련없이 그래프 내에서 무한 반복을 빠져나올 수 없는 경우가 발생할 수 있는데요. 예를들어 우리가 찾고자 하는 사람이 아닌 두 사람이 있다고 생각해봅시다. 이 두 사람은 자기가 우리가 찾고자 하는 사람이 아니라면 이웃을 추가하겠죠. 그리곤 다음 번에 그 이웃으로 갔는데 그 이웃은 또 우리가 찾고자 하는 사람이 아니므로 조금 전 저희가 살펴봤던 사람을 아웃으로 추가하는 것입니다. 이렇게 계속 오고가며 반복하면 결국 무한반복이 되겠죠.

그렇기 때문에 확인한 사람의 명단을 만들고 확인하지 않았던 사람들 중 내에서 우리가 찾고자 하는 사람을 찾는 작업을 반복해야 하며 확인한 사람이라면 명단에 체크하여 다음에 그 사람을 탐색하지 않도록 표시해두어야 하는 것입니다.

 

너비 우선 탐색(BFS)은 여기까지 알아보겠습니다. 이에 대해 이해나 깨달음이 좀 더 깊어지면 그 때 추가기록할게요!

 

---

1 본 내용은 'Hello Coding 그림으로 개념을 이해하는 알고리즘' 을 참고하였습니다.↩