[백준 3190] 뱀

문제 바로가기

3190번: 뱀

 

푸는데 1시간 20분 걸렸다.

더 줄일 수 있었는데 이상한데서 시간 낭비했다 ㅠㅠ

뱀의 방향 전환정보에서 X와 C의 의미를 잘 생각해야한다.

 

X초가 지난 후에 C의 방향을 전환하기 때문에 시작은 0초부터이고

마지막에는 현재 시간부터 (현재시간 + 최대 N길이)동안 move_snake를 한 번 더 해주어야한다.

 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, K, L;
int map[101][101];
int pos[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int c_dir = 0;
int cx = 1, cy = 1;
int gtime;
int time_limit;
int end_time;
queue<pair<int, int>> snake;

bool isIn(int x, int y)
{
	if (x >= 1 && x <= N && y >= 1 && y <= N)
		return true;
	return false;
}

void move_snake(int x, int y)
{
	if (gtime == time_limit)
	{
		cx = x;
		cy = y;
		return;
	}
	
	int nx = x + pos[c_dir][1];
	int ny = y + pos[c_dir][0];

	if (!isIn(nx, ny) || map[ny][nx] == 1)
	{
		end_time = gtime + 1;
		return;
	}
	else
	{
		if (map[ny][nx] == 2)// eat apple
		{
			map[ny][nx] = 1;
			snake.push({ ny, nx });
		}
		else
		{
			pair<int, int> remove_snake = snake.front();
			map[remove_snake.first][remove_snake.second] = 0;
			snake.pop();
			snake.push({ ny, nx });
			map[ny][nx] = 1;
		}

		gtime++;
		move_snake(nx, ny);
		
	}
}

int main()
{
	cin >> N >> K;
	
	for (int i = 0; i < K; i++)
	{
		int a, b;
		cin >> a >> b;
		map[a][b] = 2;
	}

	map[1][1] = 1;
	snake.push({ 1,1 });

	cin >> L;
	for (int i = 0; i < L; i++)
	{
		int n_dir;
		int X;
		char C;
		cin >> X >> C;

		time_limit = X;

		move_snake(cx, cy);

		if (end_time != 0)
		{
			cout << end_time << endl;
			return 0;
		}

		if (C == 'D')
			n_dir = 1;
		else if (C == 'L')
			n_dir = 3;

		c_dir = (c_dir + n_dir) % 4;
	}

	time_limit = gtime + 100;
	move_snake(cx, cy);

	cout << end_time << endl;
	return 0;
}