안녕하세요 기린입니다 :)
오늘은 배울 알고리즘은 바로 너비 우선 탐색(Breadth-Frist Search, BFS)은 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 입니다. 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법입니다. 너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용합니다. 준비물은 큐(Queue)인데요 아래와 같이 큐와 그래프를 준비해보도록 합시다.
BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작합니다. 또한 시작 노드를 방문 했다고 '방문 처리' 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다.
이제 BFS는 다음과 같은 간단한 알고리즘에 따라서 작동합니다.
1. 큐에서 하나의 노드를 꺼냅니다. (방문 처리)
2. 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다.
위 1번과 2번을 계속 반복해주시면 됩니다 :)
먼저 시작 노드 1을 큐에서 꺼내고(방문 처리) 1의 주변 노드인 2와 3이 모두 방문된 적이 없으므로 큐에 넣어주겠습니다. 결과는 위 사진과 같습니다. 그 다음 BFS를 실행시켜보죠
큐에서 2를 꺼낸 직후에는 그 인접한 노드는 3, 4, 5중에서 1과 3은 이미 방문한 적이 있으므로 넘어가고 4와 5를 큐에 삽입합니다. 그 결과 형태는 위 그림과 같습니다.
이후에 노드 3을 큐에서 꺼낸 뒤에 방문처리해주고, 3과 인접한 노드인 6과 7을 큐에 삽입합니다. 노드 1과 2는 방문한 적이 있으므로 6과 7만 큐에 넣어주면 됩니다. 따라서 위와 같이 기본적으로 모든 노드가 방문처리가 되었습니다. 이제부터 남은 노듣들을 큐에서 꺼내주기만 하면 됩니다.
자 이제 차례대로 꺼내면 위와 같이 나옵니다. 큐에서 꺼낸 순서를 보시면 1, 2, 3, 4, 5, 6, 7입니다. 아무렇게나 막 탐색하는 것이 아니라 1부터 '가까운' 노드들부터 탐색이 이루어진다는 점에서 너비 우선 탐색이라고 합니다. 거리가 먼 노드인 4, 5, 6, 7은 가장 마지막에 탐색이 이루어지게 됩니다. 이제 소스코드로 구현해볼건데요 여기서 큐를 직접 구현하지 않고 C++ STL 라이브러리를 사용해주도록 하겠습니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// visit array
int c[7];
vector<int> a[8];
void bfs(int start) {
queue<int> q;
q.push(start);
c[start] = true;
while(!q.empty()) {
int x = q.front();
q.pop();
printf("%d ", x);
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (!c[y]) {
q.push(y);
c[y] = true;
}
}
}
}
int main(void) {
// Connect 1 and 2
a[1].push_back(2);
a[2].push_back(1);
// Connect 1 and 3
a[1].push_back(3);
a[3].push_back(1);
// Connect 2 and 3
a[2].push_back(3);
a[3].push_back(2);
// Connect 2 and 4
a[2].push_back(4);
a[4].push_back(2);
// Connect 2 and 5
a[2].push_back(5);
a[5].push_back(2);
// Connect 3 and 6
a[3].push_back(6);
a[6].push_back(3);
// Connect 3 and 7
a[3].push_back(7);
a[7].push_back(3);
// Connect 4 and 5
a[4].push_back(5);
a[5].push_back(4);
// Connect 6 and 7
a[6].push_back(7);
a[7].push_back(6);
// Perform BFS
bfs(1);
return 0;
}
위와 같이 크기가 8인 배열 a를 vector로 선언하고 방문여부를 true, false로 확인하는 c 배열을 선업합니다. STL 라이브러리인 Queue를 이용하여 너비 우선 탐색을 수행하는걸 보실 수 있습니다.
BFS는 너비를 우선으로 하여 탐색한다는 특성이 중요한 것이고, 이를 이용해 다른 알고리즘에 적용한다는 것이 핵심입니다. :]
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
