1-8. 오른손 법칙 개선하기

0. 시간 복잡도

(1) 동적 배열 ; vector

(1-1) push_back : O(1) - 상수 초

(1-2) 중간 삽입 / 삭제 : O(N) - 요소의 개수 만큼 복사 / 이동이 발생

(1-3) 임의 접근 : O(1)

 

(2) 이중 연결 리스트 ; list

(2-1) 삽입 / 삭제 : O(1)

(2-2) 임의 접근 : O(N) - 요소의 포인터를 타고 타고...

 

(3) 스택 : O(1)

(4) 큐 : O(1)

 

1. 오른손 법칙 개선

지금의 우수법 방법은 갈 필요가 없는 곳도 진행해야한다.

따라서 앞으로 갈 곳에 대한 정보를 스택에 저장해서 사용한다.

(1) Player.cpp

void Player::Init(Board* board)
{ //~~~~
	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();
	}

	reverse(path.begin(), path.end());
	_path = path;
}

이전에 지나온 경로를 하나씩 _path에 저장해왔는데 그 것을 이용하는 방법이다.