[Linear Data] Chapter 05. 오른손 법칙 개선

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

오른손 법칙 개선 · developeSHG/Data_Structure-Algorithm@32793de

 

결과물

 

 

---

 

 

이전 카테고리인 Maze(미로)를 만들었을 때, 길찾기 알고리즘으로 오른손 법칙을 이용했다.

하지만 아쉬운 점은 막힌 길을 굳이 갈 필요가 없음에도 불구하고, 우수법 특성상 막힌 길에 들어갔다 다시 나온다는 것이 비효율적이다.

최단 거리까진 아니라도 불필요하게 이동하는 현상을 예방할 수 없을까 생각이 드는데, 이전에 학습한 stack의 특성을 통해 최적화할 수 있다.

 

어떤 방식으로 개선이 가능하냐면 이동을 할 때마다, 지금까지 내가 걸어온 길을 stack으로 추적할 것이다. stack으로 관리하면서 걸어온 길을 stack에 삽입하기 전에, 기존에 목적지까지 가야할 경로를 담아두고 있는 path와 비교한다.

현재 좌표에서 다음으로 가야할 좌표가 stack 최상위(top)에 있는 원소와 동일한지를 비교하는 것이다.

만약에 다르면 stack에 삽입하면 되고, 같다고 하면 거꾸로 돌아간다는 의미이기 때문에 stack 최상위 원소는 pop을 해줘 경로를 최소화할 수 있다.

 

void Player::Init(Board* board)
{
	_pos = board->GetEnterPos();
	_board = board;

	Pos pos = _pos;

	_path.clear();
	_path.push_back(pos);

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

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

	while (pos != dest)
	{
		// 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인.
		int32 newDir = (_dir - 1 + DIR_COUNT) % DIR_COUNT;
		if (CanGo(pos + front[newDir]))
		{
			// 오른쪽 방향으로 90도 회전.
			_dir = newDir;
			// 앞으로 한 보 전진.
			pos += front[_dir];

			_path.push_back(pos);
		}
		// 2. 현재 바라보는 방향을 기준으로 전진할 수 있는지 확인.
		else if (CanGo(pos + front[_dir]))
		{
			// 앞으로 한 보 전진.
			pos += front[_dir];

			_path.push_back(pos);
		}
		else
		{
			// 왼쪽 방향으로 90도 회전.
			_dir = (_dir + 1) % DIR_COUNT;
		}
	}

	stack<Pos> s;

	for (int i = 0; i < _path.size() - 1; i++) // 목적지는 제외하기 때문에 size에서 -1
	{ 
		// 이전에 걸어온 길이 있었다하면 걸어온 길의 최상위 원소와, 다음으로 가야할 길이 일치하면 되돌아가고 있다는 것이기 때문에 pop
		if (s.empty() == false && s.top() == _path[i + 1]) 
			s.pop();
		else
			s.push(_path[i]);
	}

	// 목적지 도착
	if (_path.empty() == false)
		s.push(_path.back());

	vector<Pos> path;
	while (s.empty() == false)
	{
		path.push_back(s.top());
		s.pop();
	}

	std::reverse(path.begin(), path.end()); // stack은 선입선출이라 목적지부터 push 되었기 때문에, 거꾸로 reverse해줌.

	_path = path;
}