[알고리즘] 너비 우선 탐색 (BFS)

[알고리즘] 너비 우선 탐색 (BFS)

---

너비 우선 탐색(Breadth First Search, BFS)은 맹목적 탐색을 하고자 할때, 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용하며 먼저 들어온 것을 먼저 처리해준다는 점에서 큐를 이용한다.

다음 숫자들을 너비 우선 탐색하는 프로그램을 작성하자!

1. 큐에서 하나의 노드를 꺼낸 후 방문 처리를 한다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

소스코드 구현 (C++)

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void BFS(vector<int>* arr, int start)
{
	int size = arr->size();
	queue<int> q;
	q.push(start);
    //체크용
	bool c[10000] = { false };
    //처음부터 체크하면서 노드를 검사하면서 들어간다
	c[start] = true;
	cout << "BFS : [ ";
	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		cout << front << ' ';
		for (int i = 0; i < arr[front].size(); i++)
		{
			int node = arr[front][i];
			if (!c[node])
			{
				q.push(node);
				c[node] = true;
			}
		}
	}
	cout << "]" << endl;
}

int main()
{
	int size;
	
	vector<int> arr[7];
	arr[0].push_back(1);
	arr[0].push_back(2);

	arr[1].push_back(2);
	arr[1].push_back(3);
	arr[1].push_back(4);

	arr[2].push_back(1);
	arr[2].push_back(5);
	arr[2].push_back(6);

	arr[3].push_back(1);
	arr[3].push_back(4);

	arr[4].push_back(1);
	arr[4].push_back(3);

	arr[5].push_back(2);
	arr[5].push_back(6);

	arr[6].push_back(2);
	arr[6].push_back(5);

	BFS(arr, 0);
	return 0;
}

출력 결과

---

BFS는 너비를 우선으로 탐색한다는 특성이 중요한 알고리즘으로 자체적으로 유용하기보다는 다른 알고리즘에 적용하는 것이 핵심이다. 게임에서 맵의 최단거리를 구할때 사용하면 좋을 것 같다.