[Graph] Chapter 04. BFS를 이용한 길찾기 구현

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ce84719bc1e67974dda74fb833ac50e526c8fe19

BFS를 이용한 길찾기 구현 · developeSHG/Data_Structure-Algorithm@ce84719

 

결과물

 

 

---

 

 

이전 글에서 구현한 BFS를 토대로 Maze(미로) 글에 길찾기를 적용했던 우수법을 BFS로 교체해보자.

우수법 결과물

 

이전에 BFS를 구현할 때, Vertex라는 점을 만든 다음 인접리스트 혹은 인접행렬을 토대로 관리했었다. 대부분의 경우에는 실제 정점정보와 인접정보를 구분해서 만드는 것이 조금 더 활용하기 편하다고 했다.

 

하지만, 경우에 따라서는 정점이건 인접정보이건 둘을 아예 만들 필요도 없고, 기존에 있던 정보를 토대로 유추할 수 있다. 위의 미로를 살펴보면 각 칸에 대한 정보를 알고있다. 그리고 맵이 어떻게 생겼는지 큰 그림도 알 수 있다.

거꾸로 각 칸들을 정점이라고 가정해보자.

비록 정점 정보와 인접리스트, 인접행렬을 만들어 준 적은 없지만, 맵의 정보를 이용해서 Graph로 표현할 수 있다. 즉, 모든 칸들이 정점이라고 가정하고, 상하좌우 네 방향으로 기본적으로 연결이 되어있으니 인접하다고 판단할 수 있다.

 

그럼 시작점에서 BFS를 실행했을 때, 가장 가까운 정점 순으로 방문을 할 것이고, 목적지를 방문했을 때, 자신의 Parent가 누구였는지를 역으로 타고 올라가면서 최단 경로 탐색을 완료할 수 있다.

 

void Player::Bfs()
{
	Pos pos = _pos;

	// 목적지 도착하기 전에는 계속 실행
	Pos dest = _board->GetExitPos();

	Pos front[4] =
	{
		Pos { -1, 0},	// UP
		Pos { 0, -1},	// LEFT
		Pos { 1, 0},	// DOWN
		Pos { 0, 1},	// RIGHT
	};

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

	//vector<vector<Pos>> parent;
	// parent[A] = B; -> A는 B로 인해 발견함
	map<Pos, Pos> parent;

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

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

		// 방문!
		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);
			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());
}