미로 - 오른손법칙 개선

미로 - 오른손법칙 개선 (stack)

• 앞서 만들어본 오른손법칙을 통한 미로 길찾기는 불필요한 길을 지나는 것이 불가피한 알고리즘이였다.

• stack을 이용하면 최단루트를 구할 순 없지만 막다른 길에서 되돌아 오는 것을 방지하는 길을 알아낼 수 있다.

	stack<Pos> s;
	for(int i=0;i<_path.size()-1;i++)
	{

		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());

	_path = path;

• 현재 위치를 i라고 할 때 스택에 저장되어 있는 (i - 1) 번 째 루트와 (i + 1)번 째 루트를 비교하여 서로 같다면 되돌아 오는 길이므로 최종 루트에서 삭제한다.

• 같지 않다면 스택에 현재 위치인 i 번째 루트를 저장한다.

• 모든 길찾기가 끝난 후 최종 루트에 스택에 저장된 루트를 저장한다. 이 때 stack은 맨 뒤의 원소부터 꺼내므로 임시 변수에 저장한 후 reverse를 하여 최종 루트에 저장한다.

• 이 방식을 사용하면 기존의 오른손 법칙을 통해 구한 루트 중 되돌아 오는 루트를 없앨수 있다.

• 하지만 막다른 길에 마주하여 되돌아 오는 길만 줄인다뿐이지 최단루트를 구할 수 있는 알고리즘은 아니다.

결과

• 기존의 오른손 법칙을 통한 길찾기 보다 훨씬 빠르게 도착하는 것을 볼 수 있다.