[알고리즘] 깊이우선탐색(Depth-First Search)과 너비우선탐색(Breadth-First Search) (2)

오늘의 포스팅 내용은 저번의 깊이우선탐색(Depth-First Search)에 이어서 너비우선탐색(Breadth-First Search)이다.

깊이우선탐색(DFS)와는 다르게 너비우선탐색(BFS)은 큐를 사용한다.

이번에도 역시 다음과 같은 상황이 있다고 해보자. 

이 상황에서  L을 찾아줘! 라는 요구사항이 있다면 답을 찾기위해 BFS는 어떻게 동작할까?

너비우선탐색의 정의는 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 

라고 위키백과에 써있다.

너비우선탐색은 노드를 선택하고 추가하는 과정에서 큐을 사용한다. 

그리고 너비우선탐색 이라는 말이 맞게 우선적으로 가능한 넓게 확인하면서 내려가는 방법으로 탐색한다. 

 

Step1. 우선 출발점인 A를 큐에 넣는다.

Step2. 그 후, 큐의 제일앞인 A를 꺼내고 A와 연결된 B와 C를 큐에 넣는다. (어떤것을 먼저 넣을지는 개발자 마음이다.)

나는 알파벳이 작은것부터 큐에 먼저 넣는 방식으로 B를 넣고 C를 넣었다.

그러면 큐의 내용은 다음과 같다.

Step3. 다음 방법은 역시 큐의 제일 앞인 B를 꺼내고 B와 연결된 노드들( D, E )을 큐에 넣는다.

( A의 경우 이미 큐에 한번 들어갔다 나온 데이터이기 때문에 다시 큐에 넣지 않는다.) 

그러면 그림은 다음과 같아진다.

Step4.

그다음 큐의 최상단인 C를 꺼내고 C와 연결된 노드들( F, G )을 큐에 넣는다.

Step5.

D를 꺼내고 D와 연결된 노드들을 검색해 보니 H와 I가 있으니 큐에 넣어준다.

Step5.

E 역시 Step5 와 마찬가지 이다. 

 

 

Step6.

큐의 제일앞에 있는 F를 꺼내고 그와 연결된 노드들을 확인하는데 L이 있다!! 드디어 L을 발견했다!!

Step 들을 따라가면서 느꼈겠지만 너비우선탐색은 글자그대로 너비를 우선시하면서 탐색하는 것이라 

넓게 가로로 모든 가능성을 다 찾은후에 한단계 깊이 내려가서 다시 찾는 방식이다.

그리고 이러한 방식으로 찾기 위해서 큐을 사용한다! 너비우선탐색은 이게 끝이다!

이번장을 통해서 왜 너비우선탐색이 큐를 사용하는지만 이해하면 다 이해한거다.

 

 

 

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~​