탐색 알고리즘 BFS 너비 우선 탐색 [코딩 테스트, 코딩 면접 준비]

BFS(Breath First Search)란?

너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS(Depth First Search)는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 BFS는 그 반대이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

아래와 같은 그래프를 예를 들어 노드 1을 시작으로 BFS 알고리즘 이용하여 탐색을 진행 해보자.

 

[step 1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.

step 1

[step 2] 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.

step 2

[step 3] 큐에서 노드 '2'를 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.

step 3

[step 4] 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4'와 '5'를 모두 큐에 삽입하고 방문 처리를 한다.

step 4

[step 5] 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

step 5

[step 6] 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 한다.

step 6

[step 7] 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.

step 7

결과적으로 노드의 탐색 순서는 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6 이다.

너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS 보다 좋은 편이라는 점까지만 추가로 기억하자.

BFS 알고리즘 예제

https://developercc.tistory.com/14

[탐색 알고리즘 BFS 너비 우선 탐색] 예제 자바 코드 (코딩 테스트, 코딩 면접 준비)

 

References

「이것이 코딩테스트다」 - 한빛미디어 (나동빈 저)

DFS(Depth First Search) 알고리즘 알고 싶다면?

https://developercc.tistory.com/10

탐색 알고리즘 DFS 깊이 우선 탐색 [코딩 테스트, 코딩 면접 준비]