출처: http://blog.naver.com/powersilk/10168065952
[경로탐색 알고리즘]
큐를 이용한 너비우선탐색 알고리즘(BFS - Breath First Search)
O. 들어가며
경로탐색 또는 길찾기 알고리즘을 공부할 때에 가장 기본적으로 이해하고 알고있어야 할 알고리즘은 깊이우선탐색(Depth First Search)과 너비우선탐색(Breath First Search)이다. 물론 실제 게임에서의 경로찾기는 A*알고리즘 등 최단경로 찾기 알고리즘을 사용한다. 혹은 네비게이션 맵을 이용하여 그래프를 구성하고 경로찾기를 구현하는 경우도 많이 있다. 이유는 A* 알고리즘이나 네비게이션 방법이 탐색 속도에서 훨씬 빠르기 때문이다. 이외에도 유전알고리즘이나 뉴럴네트워크와 같은 휴리스틱 알고리즘을 이용하기도 한다.
그러나 스택을 이용하는 깊이우선탐색이나 큐를 이용하는 너비우선탐색은 자료구조 및 알고리즘에서 기본이 되는 부분이기 때문에 반드시 이해하고 알고있어야 하는 부분이다. 여기서는 큐를 이용한 너비우선탐색 알고리즘을 다루도록 한다. 먼저 큐에 대한 설명을 간단히 하고, 큐를 이용한 너비우선탐색 알고리즘이 어떻게 동작하는지 살펴보도록 하겠다.
O. 큐(Queue)
큐는 스택과 함께 자료구조에서 꼭 이해하고 있어야할 부분 중의 하나이다. 큐는 FIFO(First-In, First-Out), 즉, 선입선출 방식의 자료구조이다. 프로그램으로 구현할 때에는 tail(or rear)에서 데이터 삽입이 진행되고, front에서 데이터가 삭제된다. 배열을 이용한 큐의 추상자료형은 다음과 같다.
enqueue(int item) 메쏘드는 tail 위치에 데이터를 추가하는 기능이고, dequeue() 메쏘드는 front 위치의 데이터를 제거하는 기능이다. 큐를 프로그램 코드로 작성하는 것은 큐에 대한 포스팅에서 자세히 다루도록 하겠다.
O. 너비우선탐색 (Breath First Search)
너비우선탐색은 시작 노드를 먼저 방문한 후 시작 노드에 인접한 모든 노드들을 우선 방문하는 방법으로 트리 또는 그래프에서 동일한 레벨에 있는 노드를 먼저 탐색하는 방법이다. 이에 따라 출발 노드에서 목표 노드까지의 최단 경로 찾기가 가능하다. 그러나 그래프의 사이즈가 클 경우 탐색 가지가 급격히 증가함에 따라 메모리 소모가 크며, 최악의 경우 모든 경로를 탐색하게 된다.
너비우선탐색은 큐를 이용하여 구현할 수 있다. 시작노드를 방문하고, 큐에 삽입한 후 큐가 빈 상태가 되거나 목적노드를 방문할 때까지 큐의 front에 있는 노드를 삭제한 후 이 노드와 인접한 노드들을 다시 모두 큐에 삽입한다. 이때 큐에 삽입되는 노드들의 Parent 노드는 큐에서 제거되는 노드로 설정한다. 이런 과정을 거치면 각 노드들의 Parent 노드가 결정되고, 목표노드에서부터 시작노드까지 Parent 노드들을 거꾸로 찾아가면 최종 경로를 찾을 수 있다. 이를 그림으로 설명하면 다음과 같다.
그래프가 다음과 같고 A를 시작노드로 하고, F를 목적노드로 할 때, 큐와 각 노드들의 Parent 노드 정보를 초기화 한다.
노드 A를 방문하고 이를 큐에 삽입한다. 그리고, A노드의 Parent 노드를 A로 설정한다.
이 때 A를 방문했다고 표시한다.
큐의 front에 있는 노드 A를 삭제하고, A와 인접한 노드 B와 G를 큐에 차례로 삽입한다. 같은 방법으로 노드 B와 노드 G의 Parent 노드를 큐에서 삭제된 노드 A로 설정한다. 노드 B와 G가 큐에 삽입될 때, 노드 B와 G를 방문했다고 표시한다.
위와 같은 방법으로 큐의 front에 있는 노드 B를 삭제하고, 이 노드와 인접한 노드 C와 E를 차례로 큐에 삽입한다. 이 때 노드 C와 E의 Parent 노드는 방금 전 큐에서 삭제된 노드 B가 된다.
최종적으로 목적 노드인 F를 방문한 후의 결과는 다음과 같다.
목적 노드까지 방문한 후에는 Parent 정보를 이용하여 시작노드까지의 경로를 거꾸로 탐색하면 된다. 목적 노드인 F의 Parent 노드는 노드 E가 되고, 노드 E의 Parent 노드는 B가 되며, 노드 B의 Parent 노드는 A가 된다. 즉, F->E->B->A가 되며 실제 프로그램에서는 이를 거꾸로 처리하면 시작노드 A에서 목적노드 F까지의 경로를 찾을 수 있다. 최종 결과의 모습은 다음과 같다.
O. 너비우선탐색 알고리즘
위에서 설명한 너비우선탐색의 알고리즘은 다음과 같다.
큐를 생성. 시작노드를 큐에 삽입하고 방문한 것으로 표시한다. 큐가 비어있지 않고 목적노드를 찾지 못하면 큐에서 front에 있는 노드를 얻어오고 이 노드와 인접한 모든 노드들을 큐에 삽입한다. 큐에 노드를 삽입할 때 삽입되는 노드들은 방문했다고 표시한다. 또한, 이 코드에서는 기술되지 않았지만, 큐에 삽입되는 모든 노드들의 Parent 노드들은 front에서 얻어온 노드로 설정한다.
O. 실행결과
아래 동영상은 자료구조 시간에 구현한 결과로 큐를 이용한 너비우선탐색 알고리즘을 이용하여 목적노드까지 탐색하는 과정을 나타내고 있다. 맵은 타일맵으로 구성되어 있으며, 검정색 타일은 벽을, 녹색 타일은 오브젝트로 하였다. 빨간 원이 너비우선탐색을 이용하여 탐색해가는 과정을 나타내고 있다.
O. 마치며
이번 포스팅에서는 큐를 이용한 너비우선탐색 알고리즘을 살펴보았다. 스택과 큐는 반드시 이해하고 알아야할 자료구조 중의 하나이다. 또한 너비우선탐색은 큐를 이용한 응용 중에 하나이며 깊이우선탐색과 더불어 길찾기알고리즘의 기본이 되는 알고리즘이다. 따라서 너비우선탐색 알고리즘의 동작원리를 이해하는 것은 매우 중요하다.
다음 포스팅에서는 지금까지 여러번 언급하였지만, 너비우선탐색 알고리즘과 함께 길찾기의 기본 알고리즘 중의 하나인 깊이우선탐색 알고리즘에 대해 살펴보도록 하겠다.
'프로젝트 관련 조사 > 알고리즘' 카테고리의 다른 글
| Gradient Descent 탐색 방법 (0) | 2017.03.06 |
|---|---|
| 컨벌루션 신경망 ( Convolutional Neural Networks, CNN ) ~ 개요 (0) | 2017.03.06 |
| [C++] [STL] vector 벡터 정리 및 예제 (0) | 2016.10.15 |
| [C++] [STL] deque 정리 및 예제 (0) | 2016.10.15 |
| [알고리즘] Backtracking (백트래킹) (0) | 2016.10.14 |