BFS (Breadth First Search) 너비 우선 탐색

BFS(너비 우선 탐색)

너비 우선 탐색은 넓게 탐색한다는 의미로 이해하면 편하다. 탐색의 경우 너무 보편적이고 코딩 테스트를 조금이라도 공부했다면 다 아는 내용이기 때문에 따로 설명은 하지 않겠다.

 

기존의 BFS를 구현할 때, 무식하게 구현하는 경우가 많았는데 역시 이 강의는 코드가 깔끔해서 좋다. 막 알고리즘을 배울때 무식하게 구현했던 나와는 다른 우아하고? 간단 명료한? 부럽다. 나도 저렇게 되야하는데...

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// DFS (Depth First Search) 깊이 우선 탐색
// 일단 갈 수 있는 방향0(깊이)을 가보고 탐색한다.
// BFS (Breadth First Search) 너비 우선 탐색
// 출발점에서 갈 수 있는 방향을 먼저 탐색 후 다음 방향을 설정한다.

struct Vertex
{
	//data
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> discoversd;
void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);
	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
}

void Bfs(int here)
{
	//누구에 의해 발견 되었나?
	vector<int> parent(6, -1);
	//시작점에서 얼만큼 떨어져 있나?
	vector<int> distance(6, -1);

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


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

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

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

		for (int there : adjacent[here])
		{
			if (discoversd[there])
				continue;

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

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

	int i = 3;
}

void BfsAll()
{
	for (int i = 0; i < 6; i++)
		if (discoversd[i] == false)
			Bfs(i);
}
void CreateGraph2()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	adjacent = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};
}
void Bfs2(int here)
{
	//누구에 의해 발견 되었나?
	vector<int> parent(6, -1);
	//시작점에서 얼만큼 떨어져 있나?
	vector<int> distance(6, -1);

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


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

	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 (discoversd[there])
				continue;

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

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

	int i = 3;
}

int main()
{
	CreateGraph();

	discoversd = vector<bool>(6, false);

	Bfs(0);
}

 

 

여기서 Parent와 distance가 가장 인상 깊었는데

 

distance를 보면 

출발 지점인 0번에서 2까지의 거리가 2번을 거쳐 가야한다는 것을 알 수 있어 최단 경로를 알 수 있게 해주는 방법을 저렇게 간단히 구현한다니..... 난 여지껏 최단거리를 구할 때, 어떤 짓을 한건지 ㅠㅠ

 

0번에서 2번을 가기 위해선 2개의 노드를 통해 가야한다. 그러면 어떻게 가는지에 대한 경로는 어디서 얻을 수 있을까?

여기 parent를 보면 도착점 2번은 1번, 1번은 0번을 통해 올 수 있다는 것을 확인할 수 있다. 그러므로 도착점 2는 출발점 0에서 거리는 2 distance이며, 경로는 0 -> 1-> 2 이다.  강의를 들으면 이런게 좋다. 시야가 넓어져.