Breadth-first search 기본개념

알고리즘 공부를 시작하면서 생소한 단어들이 너무나 많고 개념도 잡히지 않은 상태 이기 때문에 간단히 정리 하고자 한다. 우선 넓이우선탐색(BFS)은 트리를 예로 들어서 많이 설명해 주는 것 같았고 반대되는 개념으로는 깊이우선탐색(Depth-First Search) 있다. 단어 뜻 그대로 가장 깊은곳을 먼저 탐색하느냐 or 내 주위에 가까운 곳부터 전부 탐색하고

다음 깊이의 단계를 탐색 할 것 인지를 구분하고 있다. 

 

 

넓이 우선 탐색

은 물결처럼 퍼지듯 가까운 경로의 후보부터 탐색을 한다고 하는데 아래의 그림을 보면 바로 이해는 된다.

 

[그림 출처 :  https://namu.wiki/w/BFS]

위의 그림에서 처럼 BFS 는 depth 가 같은 노드를 먼더 탐색하고 다음 depth로 이동 한다. 그런데 두 탐색알고리즘의 장점은 무엇일까??

 

장점 

1. BFS를 사용하면 탐색중 목적지를 찾자마자 최단경오임이 보장되어 탐색을 바로 종료 할 수 있기 때문에 DFS에 비해 빠른경우가 많다.

2. 보통 재귀를 사용하는 DFS이 비해서 queue를 사용하기 때문에 스탤오버플로에서 비교적 자유롭고 힙 공간을 넓게 쓸 수 있어서 좀 더 넓은 범위 탐색에 유리하다. 

 

사실 BFS를 찾아본 이유는 알고리즘 문제에서 목적지에 도달하는 최단 경로를 찾는 알고리즘 문제들의 풀이 과정을 찾다보니 대부분 BFS로 풀고 있었고 그래서 어떤 알고리즘 인지 궁금해 졌다. 나는 단순히 모든 경오를 전부 구해서 가장 짧은 경로를 답으로 출력하려고 했었는데 그러다 보니까 당연히 재귀를 사용하게 됬는데... 이경우 가장 빠른 경로를 찾아도 나머지 모든길을 탐색해야 비교가 가능하기 때문에 위에서 설명한 내용처럼 BFS보다 느릴 수 밖에 없었다. 근데 신기한건 나는 DFS를 몰랐는데 그냥 내가 생각하는 사고방식이 DFS였던 것이다...  과연 나만 그럴까...?  아니면 알고리즘을 모르는 일반 사람들은 모두 DFS로 먼저 접근을 할까??? ㅎㅎ 궁금하다... 이제 방법을 알았으니 ㅎㅎ 로직 구현은 내 머리로~! (사실 BFS를 아는 것 만으로도 너무나 큰 팁을 받아서... 정답을 금방 찾을 수 있을 것 같다~! ) 오늘도 어제의 나보다 조금은 더 성장했으니 너무 조급해 하지말고 꾸준하게 공부하자!!