BFS

CJB_ny·2022년 11월 30일

BFS

DataStructure & Algorithm

목록 보기

9/35

너비 우선 탐색이라고도 한다.

그냥 출발점부터 가장 가까이 있는 녀석들 부터 탐색하려는 경향이 있다고 보면은 된다.

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

BFS

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

바로 기본 코드를 보도록 하자.

코드

vector<bool>		discovered;
vector<vector<int>> adjacent;

void CreateGraph()
{
	adjacent = vector<vector<int>>(6);
	discovered.resize(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);
	discovered[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 (discovered[there])
				continue;

			q.push(there);
			discovered[there] = true;
			
			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}	
}

void main()
{
	CreateGraph();

	BFS(0);

	return;
}

현재 방문을 위한 vector discovered, 인접 노드확인을 위한 adjacent.

그리고 Graph를 만들어주는 함수 CreateGraph를 보면은

이런 형태이다.

그리고 main함수에서 이부분을 실행을 해주면은

이와같은 결과가 나오게된다.

그러면 이것을 길찾기에 적용 시켜보도록 하자.

길찾기에 적용

이 노랭이가 파란점까지 어떻게 길을 찾을지 BFS로 탐색을 하여 찾도록 할 것이다.

이전에는 vector로 인접한 노드들을 나타냈다면 현재 맵을 그리는 부분 자체가 좌표라 봐도 무방하니 이대로 진행을 해도 될거같다.

void Player::BFS()
{
	POS pos = _pos;
	DIR dir = _dir;

	POS dest = p_board->GetExitPos();

	POS front[4] =
	{
		POS {0, -1},
		POS {-1, 0},
		POS {0, 1},
		POS {1, 0}
	};

	const int32 size = p_board->GetSize();
	vector<vector<bool>> discovered(size, vector<bool>(size, false));

	map<POS, POS> parent;

	queue<POS> q;
	q.push(pos);
	discovered[pos.y][pos.x] = true;
	parent[pos] = pos;

	int count = 0;

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

		// 방문
		cout << "방문함 : " << pos.y << " , " << pos.x << endl;

		if (pos == dest)
			break;

		for (int32 dir = 0; dir < 4; ++dir)
		{
			POS nextPos = pos + front[dir];

			// 갈 수 있는 곳인지 아닌지 체크
			if (Cango(nextPos) == false)
				continue;

			// 이미 발견한 지역인지 확인.
			if (discovered[nextPos.y][nextPos.x])
				continue;

			q.push(nextPos);
			++count;
			discovered[nextPos.y][nextPos.x] = true;
			parent[nextPos] = pos;
		}
	}
	
	_path.clear();

	// 거꾸로 거슬러 올라간다
	pos = dest;
	
	while (true)
	{
		_path.push_back(pos);

		// 시작점은 자신이 곧 부모이다.
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

	std::reverse(_path.begin(), _path.end());

	cout << count << endl;
}

이해가 잘 가지 않는다면은

이런식으로 직접 그려가면서 하는게 좋을듯하다.

내가 이해가 안되었던점

본인은 로직은 이해가 가는데 중간에


	// 거꾸로 거슬러 올라간다
	pos = dest;
	
	while (true)
	{
		_path.push_back(pos);

		// 시작점은 자신이 곧 부모이다.
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

	std::reverse(_path.begin(), _path.end());