[C++ 자/알 Note] 오른손 법칙 개선 (미로 탐색)

기존 오른손 법칙은 아래와 같다

https://motivelessstudy.tistory.com/560

[C++ 자/알 Note] 오른손 법칙

 

이렇게 길을 출력을 해보면,

탐색하기 위해 돌아간 길까지 다 출력되기에

이를 제거를 하기 위해서

스택을 활용하면 된다

 

_path vector에 저장된 모든 경로를

처음부터 돌면서

스택의 top과 _path에 다음 가야 하는 길을 비교해서

같은 경우에는 top을 제거하는 pop을 하고

그렇지 않은 경우에만 push를 하면

이를 해결할 수 있다

 

예를 들어서

1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 9 -> 10

위의 순서대로 1에서 출발해 10의 목적지에 도착했다고 가정하면

스택에 1을 쌓은 후,

2를 쌓을지 결정을 스택의 top(1)과 2 다음 인덱스(3)와 비교를 통해 하는 것이다

 

그래서 이렇게 쌓다보면

스택에 1 2 3 4까지 쌓여 있는 상태에서

5를 쌓으려고 하면

스택의 top(4)와 5 다음 인덱스(4)가 같기 때문에 

스택에서 4가 pop 되는 것이다

 

위의 방식을 진행하면 우리가 원하는 결과를 얻으며

코드는 아래와 같다

stack<Pos> s;

for (int i = 0; i < _path.size() - 1; i++)
{
	// 스택의 top과 _path에 다음 가야하는 길 비교
	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;