너비우선탐색이 무엇인지에 알기 위해선 먼저 그래프에 대해 이해해야 한다.
그래프는 데이터를 저장하기 위한 자료구조 중 하나로, 다음과 같은 형태를 하고 있다.
데이터가 보관되는 장소를 정점(vertex, node)라고 하며 정점과 정점을 이어주는 선을 간선(edge)라고 한다.
(1,2)나 (1,3)은 간선이 존재하여 서로 연결되어 있지만, (3,4)는 간선이 존재하지 않으므로 서로 연결되어 있지 않은 것이다.
그래프를 "탐색한다" 는 것은 하나의 정점에서 모든 정점을 방문하는것을 말하며, 이를 통해 수많은 문제를 해결할 수 있다.
예를 들어, 미로의 길을 찾는다거나, 어떤곳에서 다른곳으로 이동하는 최소길이를 구한다거나 하는 등이 그 예이다.
너비우선탐색은 그래프를 탐색하기 위한 방법 중 하나로, 한 정점이 주어졌을때 주어진 정점에서 가까운 인접정점부터 방문하는것이 그 특징이다.
인접정점들을 방문하기위해 너비우선탐색은 큐(queue) 자료구조를 이용한다.
너비우선탐색의 진행과정은 다음과 같다.
1. 정점 1에서 방문한다고 가정할 때, 해당 정점을 큐에 삽입한다.
2. 큐에서 정점을 뽑은다음 방문처리한다.(visited배열에 삽입한다.) 이후 정점 1의 인접 정점인 정점 2와 정점 4를 큐에 삽입한다.
3. 큐에서 다음 정점인 2번 정점을 뽑은다음 방문처리한다. 이후 2번 정점의 인접 정점인 1번과 3번 정점을 큐에 삽입하는데, 1번 정점은 이미 방문하였던 기록이 있으므로, 삽입하지 않는다.(visited배열에 존재하므로)
4. 큐에서 다음 정점인 4번 정점을 뽑은다음 방문처리한다. 4번 정점의 인접 노드인 1번 정점은 이미 방문하였으므로, 삽입하지 않는다.
5. 큐에서 다음 정점인 3번 정점을 뽑은다음 방문처리한다. 3번 정점의 인접 정점인 1번 정점과 2번 정점은 이미 방문하였으므로 삽입하지 않는다.
6. 큐에 더 이상 데이터가 없으므로, 탐색을 종료한다. 탐색의 순서는 다음과 같다. (visited배열의 순서를 통해 알 수 있다)
다음과 같은 과정을 통해 가까운 정점부터 탐색하는 너비우선 탐색을 진행할수 있으며, 정점과 간선으로 구성되어 있다면 그래프의 형태는 어떤 형태로든 그릴 수 있다.
아래 gif를 보면 BFS에 대해 쉽게 이해할 수 있을 것이다.
'CS' 카테고리의 다른 글
| 스택에 대해 알아보자 (0) | 2024.01.18 |
|---|