BOJ : 3190 뱀

 

---

[BOJ 3190(G5) 리뷰]

snake 게임을 해본적이 있을것이다.

뱀을 조종하여 사과를 먹게되면 뱀의 길이가 점점 늘어난다.

뱀이 벽에 부딪히거나 자기 몸에 부딪힌다면 게임은 끝나게 된다.

이 문제는 snake게임의 규칙을 그대로 따른다. 맵이 주어지고 사과의 위치가 주어진다.

뱀은 주어진 명령대로 이동을하다가 사과를 만나면 길이가 늘어난다.

주어진 명령에 따라 게임을 수행했을 때 몇초후에 게임이 종료되는지를 구하는 문제이다.

 

일단 명령은 큐로받았다. 뱀을 이동시키기전에 큐의 front를 확인하여 현재 소요된 시간과 명령시간을 비교하여 명령에 맞게 방향을 바꿔주도록 했다.

그다음 시간이 지나면서 뱀을 이동시키고, 사과를 먹으면 길이를 늘려주면된다.

이 때 길이를 늘려주는 작업이 조금 헷갈렸다. 처음엔 구조체를 이용해 뱀의 머리의 좌표와 꼬리의 좌표를 기록하여 수행했는데 머리의 방향과 꼬리의 방향이 다르면 뱀을 이동시키는데 문제가 생겼다.

그래서 인터넷을 참고했더니 덱을 이용했길래 나도 덱을 이용하여 풀었다.

앞으로 이동할때마다 front에 머리의 좌표를 push하고 back에 위치한 꼬리의 좌표값을 받아 0으로 만들고 pop해주면 뱀이 이동하는것처럼 꼬리는 계속해서 삭제되며 머리는 앞으로 진행할 수 있다.

꼬리를 처리하는 부분에서 시간을 꽤 사용했던 문제이다.

---

#include <iostream>
#include <queue>
#include <deque>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
#define X first
#define Y second

int board[101][101] = { 0, };
int N,K,L;
queue <pair<int, char>> command;
deque <pair<int, int>> snake;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> N;
	cin >> K;
	while (K--)
	{
		int a, b;
		cin >> a >> b;
		board[a][b] = 1;
	}

	board[1][1] = 2;
	snake.push_front({ 1,1 });

	cin >> L;
	while (L--)
	{
		int T;
		char c;
		cin >> T >> c;
		command.push({ T,c });
	}

	int hdir = 0;
	int tdir = 0;
	int cnt = 0;
	while (1)
	{
		if (!command.empty())
		{
			int time = command.front().first;
			char direct = command.front().second;
			if (cnt == time) //명령에 도달
			{
				if (direct == 'D')
				{
					hdir = (hdir + 1) % 4;
				}
				else if (direct == 'L')
				{
					hdir = (hdir + 3) % 4;
				}
				command.pop();
			}
		}

		auto cur = snake.front();

		int nx = cur.X+dx[hdir];
		int ny = cur.Y+dy[hdir];

		if (nx<1 || nx>N || ny<1 || ny>N) break; //벽에 충돌
		if (board[nx][ny] == 2) break; //몸에 충돌

		if (board[nx][ny] == 1) // 사과
		{
			board[nx][ny] = 2;
		}
		else
		{
			auto tail = snake.back();
			board[nx][ny] = 2;
			board[tail.X][tail.Y] = 0;
			snake.pop_back();
		}
		snake.push_front({ nx,ny });
		cnt++;
	}
	
	cout << cnt+1;

}