BFS에 대해 알아보자

목차

 

1. BFS 란?

 

2. BFS는 언제 사용할까?

 

3. BFS는 어떻게 사용할까?

 

4. BFS는 왜 사용할까?

 

5. BFS의 장점, 단점

---

1. BFS란?

BFS는 Breadth Frist Search의 약자로 너비 우선 탐색이라는 의미를 지닌다. 책에서는 가까운 노드부터 탐색하는 알고리즘이라고 쓰여져있는데, 이를 쉽게 풀어 예시를 들면 아래와 같다. 물론, 예시는 정의와 100%일치하는 것이 없으므로 맥락을 이해하는데에만 참고해야할 것이다.

철수가 갈림길이 무수히 많은 어딘가에 떨어져 집을 찾으려고 하고 있다.
갈림길은 모든 분기점에서 무조건 a, b, c 세개로 나누어진다.
가정으로 철수의 집이 c-a에 있다고 가정해보자.

이 전제 조건으로 집을 빠르게 찾을 수 있는 알고리즘인 BFS를 사용해보자.
-------------------------------------------------------------------------------------------
1. 철수가 a, b c중에서 a를 골라 진행한다. 여기에는 철수의 집이없다. 초기로 돌아간다.

2. 철수가 b를 골라 진행한다. 여기에는 철수의 집이없다. 초기로 돌아간다.

3. 철수가 c를 골라 진행한다. 여기에는 철수의 집이없다. 초기로 돌아간다.

4. 철수는 a-a, a-b, a-c를 확인했다. 이 중에는 철수의 집이 없다.

5. 철수는 다시 처음으로 돌아가고 이번엔 b로 진행한다.

6. 철수는 b-a, b-b, b-c를 확인했다. 이중에는 철수의 집이 없다.

7. 철수는 다시 처음으로 돌아가고 이번엔 c로 진행한다.

8. 철수는 c-a가 집이란걸 확인했고, 그 즉시 알고리즘은 끝이난다.

 

2. BFS는 언제 사용할까?

BFS는 두 노드 사이의 최단 경로를 찾을 때 사용된다. 

 

3. BFS는 어떻게 사용할까?

일반적으로 큐 자료구조를 이용한다. 큐 자료구조는 선입선출 방식으로 데이터가 처리되는데, 위의 예제로 예시를 들어보겠다.

철수가 c-a에 있는 집을 찾기 위한 여정을 큐에 담아 표현해보자

1. 초기 위치에서 갈림길 a, b, c 확인
-> 큐 = { a, b, c}

2. a에서 a-a, a-b, a-c를 확인. a는 확인하고 없어짐.
-> 큐 = { b, c, a-a, a-b, a-c }

3. b에서 b-a, b-b, b-c를 확인, b는 확인하고 없어짐.
-> 큐 = { c, a-a, a-b, a-c, b-a, b-b, b-c }

4. c에서 c-a, c-b, c-c를 확인, c는 확인하고 없어짐.
-> 큐 = { a-a, a-b, a-c, b-a, b-b, b-c, c-a, c-b, c-c }

5. 이 행동을 반복한다. (예: a-a를 확인&제거하고 a-a-a, a-a-b, a-a-c를 뒤에 추가)
-> 큐 = { a-b, a-c, b-a, b-b, b-c, c-a, c-b, c-c............ }

6. 철수의 집은 c-a 확인. 바로 종료
-> 큐 = { c-a, c-b, c-c, a-a-a, a-a-b, a-a-c.............. }

 

다만, 위 예제는 방문처리를 고려하지 않은 것으로 연산이 생각했던 것보다 더 연산할 가능성이 있다.

 

5. BFS는 왜 사용할까?

보통 DFS보다 BFS구현이 조금 더 빠르게 동작한다. 이 이상의 지식은 내가 알고자하는 코딩 테스트의 범위에서 벗어나므로 정리하지 않겠다.