[C++ algorithm] 스택, 큐, 오른손 법칙 개선

스택

스택은 LIFO를 따른다. 즉 Last In First Out 후입 선출을 따른다.

먼저 들어온 데이터가 나중에 나가는 구조의 자료구조이다.

 

게임에서 자주 사용하는 기능중 하나인 되돌기기 기능을 구현할 때 스택을 사용한다.

#include <iostream>
#include <stack>
using namespace std;



int main()
{
	stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	// 비었나??
	while (s.empty() == false)
	{
		int data = s.top();
		// 최상위 원소 삭제
		s.pop();
		cout << data << endl;
	}
	
	int size = s.size();
}

직접 구현해보자. 벡터를 사용하면 구현이 쉽다.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

template<typename T>
class Stack
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}
	void pop()
	{
		_container.pop_back();
	}
	T& top()
	{
		return _container.back();
	}
	bool empty() { return _container.empty(); }
	int size() { return _container.size(); }
public:
	vector<T> _container;
};

int main()
{
	Stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	// 비었나??
	while (s.empty() == false)
	{
		int data = s.top();
		// 최상위 원소 삭제
		s.pop();
		cout << data << endl;
	}
	
	int size = s.size();
}

큐(queue)

큐는 FIFO 즉, First In First Out 선입선출의 방식을 따른다.

스택에 비해 훨씬 사용 범위가 넓다.

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	queue<int> q;
	for (int i = 0; i < 10; i++)
	{
		q.push(i);
	}
	while (q.empty() == false)
	{
		int value = q.front();
		q.pop();
		cout << value << endl;
	}
	int size = q.size();
}

실제 구현을 해보겠다. 그런데 만약 vector를 통해서 구현하면 좋을 것인가는 고려해봐야한다. 왜냐하면 맨 앞에 있는 데이터를 추출해야하기 때문이다. 이는 vector에서 느리게 동작하고 있기 때문이다. List로 구현하면 다음과 같다.

#include <iostream>
#include <list>
#include <queue>
using namespace std;

template<typename T>
class ListQueue
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}
	void pop()
	{
		_container.pop_front();
	}
	T& front()
	{
		return _container.front();
	}
	bool empty() { return _container.empty(); }
	int size() { return _container.size(); }

private:
	list<T> _container;
};

int main()
{
	ListQueue<int> q;
	for (int i = 0; i < 10; i++)
	{
		q.push(i);
	}
	while (q.empty() == false)
	{
		int value = q.front();
		q.pop();
		cout << value << endl;
	}
	int size = q.size();
}

vector를 사용하고도 효율적으로 관리할 수 있는데 바로 front와 back 을 이용해서 순환구조로 만들 수 있다.

미로게임 오른손 법칙 개선

우수법을 사용하다보면 불필요한 길을 무조건 가야하는 경우가 생기곤 한다.

이걸 스택을 이용해서 개선해보겠다.

이론적으로는 내가 가는 길을 스택에 넣어서 관리하다가 스택의 최상단 데이터가 현재 내가 가는 길이다라고 판단되면 그 길을 이미 왔던 길이다라고 생각하는 것이다. 즉, path를 미리 계산하기 때문에 가능한 방법이기도 하다.

코드로 직접 보면 이해가 빠르다.

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++)
	{
		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;
}

이제는 불필요한 길을 가지않고 목적지 까지 가는 모습이다.

결과