Baekjoon 3190 뱀

Link https://www.acmicpc.net/problem/3190

소스결과 2008 KB / 0 ms

출처 Baekjoon , Croatian Highschool Competitions in Informatics 2005

언어 C++ 17

분류 시뮬레이션

 

설명

Dummy라는 도스 게임의 규칙을 적용하여 뱀이 몇 턴만에 죽는지 구해보자.

 

처음 문제를 구현 할 때 머리를 90도 회전 한다는 규칙을 90도 회전 후 1칸 진행으로 이해해 구현해 예제가 잘못됬다고 생각했었다.

머리를 90도 회전 한다는건 90도 회전하는 것으로 1턴을 소모 하는게 끝이었다. 질문 게시판에도 비슷한 사례가 있어 찾아 낼 수 있었다.

 

기존 게임에서는 머리가 꼬리 위치로 가는 순간에 죽지 않지만 이번 게임은 죽는다. 그 내용은 문제에서 제시 된 규칙만 따르면 된다.

뱀 몸의 위치를 맵에 표현 하는 것 보다 배열로 구현해 위치만 기억 하는게 더 편했다.

 

사과는 먹은 뒤에 사라진다. 이 점도 유의 하자.

 

알고리즘

1. 초기 정보를 받아온다.

2. 뱀의 현재 위치를 1,1로 초기화 하고 길이를 1로 셋팅한다.

3. 뱀의 다음 위치 정보를 받아오고 규칙에 따라 다른 내용을 진행한다.

 3 - 1. 다음 위치가 지정된 범위 밖에 가거나 자신의 몸에 박는 경우, 반복문을 종료한다.

 3 - 2. 다음 위치에 사과가 존재 하는경우 머리가 늘어난다. 꼬리는 이동하지 않는다.

 3 - 3. 다음 위치에 사과가 존재 하지 않는 경우. 꼬리를 이동시킨 후. 머리를 다음 위치로 설정한다.

4. 반복문이 종료되면 결과 값을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

struct Point
{
	short x;
	short y;

	Point() {}
	Point(short x, short y) : x(x), y(y) {};
};

const short MAX = 100;
const short T_MAX = 10000;
bool apples[MAX][MAX];
char orders[T_MAX+1];
Point snake[MAX + 1];
int snakeLen = 1;

const short posX[4] = { 0, 1, 0, -1 };
const short posY[4] = { 1, 0, -1, 0 };

void shift(short x, short y)
{
	for (int i = 0; i < snakeLen - 1; i++)
		snake[i] = snake[i + 1];

	snake[snakeLen - 1].x = x; snake[snakeLen - 1].y = y;
}

bool isCross(short x, short y)
{
	for (int i = 0; i < snakeLen; i++)
		if (snake[i].x == x && snake[i].y == y)
			return true;

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, apple, cc, res = 1;
	int look = 0;

	cin >> n >> apple;
	for (int i = 0; i < apple; i++)
	{
		short x, y;
		cin >> x >> y;
		apples[x - 1][y - 1] = true;
	}

	cin >> cc;
	for (int i = 0; i < cc; i++)
	{
		int turn;
		cin >> turn;
		cin >> orders[turn];
	}

	snake[0].x = snake[0].y = 0;

	for (; res < T_MAX; res++)
	{
		short nextX = snake[snakeLen - 1].x + posX[look];
		short nextY = snake[snakeLen - 1].y + posY[look];

		if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n)
		{
			if (isCross(nextX, nextY))
				break;

			if (apples[nextX][nextY])
			{
				apples[nextX][nextY] = false;
				snake[snakeLen].x = nextX; snake[snakeLen].y = nextY;
				snakeLen++;
			}
			else
				shift(nextX, nextY);
		}
		else
			break;

		if (orders[res])
		{
			if (orders[res] == 'D')
				look = (look + 1) % 4;
			else
				look = look - 1 < 0 ? 3 : look - 1;
		}
	}

	cout << res;

	return 0;
}