[C++ 자/알 Note] BFS를 이용한 길찾기 구현

주의사항 - 사용조건

BFS나 DFS를 통해 그래프를 탐색하는 경우

일반적으로 모든 연결관계를

인접리스트 방식이나 인접행렬 방식으로 저장한 후 사용 한다

그러나 이처럼 모든 관계를 메모리에 저장하지 않아도

본인 기준으로 갈 수 있는 방향들만 구분이 된다면

모든 연결관계를 저장할 필요는 없다

 

마치 미로를 탐색하는 경우에서

모든 길의 값을 알 필요 없이

현 위치에서의 방향만 판단하면 되는 것과 같다

 

BFS 길찾기 구현

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));// 발견여부 배열

	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] == true)
				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());// 뒤집기
	}

}