BFS - 너비 우선 탐색

  BFS ( Breadth-First Search ) 는 너비 우선 탐색이라는 탐색법이다. 이전에 포스팅한 깊이 우선 탐색과는 다르게 한 노드에 대해서 갈 수 있는 모든 노드에 대한 탐색을 같이 진행하므로 최단 거리를 찾거나 최단 루트를 찾는 문제 등에 자주 쓰이는 알고리즘이다. 

 

  모든 노드들에 대해서 한번씩 탐색을 시도하고, 해당 노드에서 탐색 가능한 모든 노드들에 대해서도 탐색을 해야하므로 큐 자료구조를 이용하여 모든 노드들에 대한 탐색을 시도하되, 먼저 탐색해야 하는 목록에 오른 노드들부터 탐색을 할 수 있게끔 구현합니다.

 

 만약 BFS를 마치고, 해당 탐색 루트 중에서 원하는 위치로 이동 가능한 최단루트를 저장해두고 싶다면, 해당 노드로 최단 비용으로 올 수 있는 바로 이전의 노드의 값을 저장하여 손쉽게 정보를 얻을 수 있습니다.

 

 그래프를 만들고, 해당 노드에 방문했는지를 찾는 vector<bool> discovered에 대한 설명은 생략하도록 하겠습니다.

void Bfs(int here)
{
	// 누구에 의해 발견 되었는지?
	vector<int> parent(6, -1);

	// 시작점에서 얼만큼 떨어져 있는지?
	vector<int> distance(6, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = true;

	distance[here] = 0;
	parent[here] = here;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited : " << here << endl;

		for (int there  = 0; there < 6; there++)
		{
			if (adjacent[here][there] == 0)
				continue;

			if (discovered[there] == true)
				continue;

			q.push(there);
			discovered[there] = true;

			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}
}

 처음 시작하기 위해 주어진 노드를 큐에 집어넣고, 해당 노드를 while문에서 꺼내어 간선이 이어진 노드들을 큐에 집어넣고 이동 비용과 거리 값을 저장합니다. 큐가 비워질때까지 ( 이동 가능한 노드가 없을 때까지) 해당 반복문을 이용하여 탐색을 완료하면 BFS가 마무리됩니다. 

 

이상으로 BFS에 대한 설명을 마치겠습니다. 포바~!