백준 3190번 - 뱀

백준 3190번 - 뱀

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

 

문제

• Snake류 게임 시뮬레이션

• 뱀은 좌회전, 우회전 가능

• 뱀이 이동할 위치에 사과가 있으면 뱀의 길이가 늘어남

• 뱀이 벽에 부딪히거나 자신의 몸에 부딪히면 게임 종료

입력

• 보드의 크기 N (2 ≤ N ≤ 100)

• 사과의 개수 K (0 ≤ K ≤ 100)

• K개의 줄에는 사과의 위치 (행,열)

• 뱀의 방향 변환 횟수 L (1 ≤ L ≤ 100)

• 뱀의 방향 변환 정보 (X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전)

• X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순

출력

• 첫째 줄에 게임이 몇 초에 끝나는지 출력

접근

• 1) 뱀이 이동할 위치를 계산한다

• 2) 뱀이 이동할 위치가 뱀의 몸이거나 벽이면 게임 종료

• 3) 뱀이 이동할 위치에 사과가 없으면 꼬리를 이동할 위치로 옮긴다. (뱀의 위치는 Queue로 구현)

• 4) 머리를 이동 시킨다

• 5) 방향 전환을 한다

C++ 코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; // 보드 크기
	int k; // 사과 개수
	int l; // 방향 변환 횟수

	int map[101][101] = { 0, }; // 맵 기본값 : 0
	pair<int, char> dir_change[101]; // 방향 변환
	int cur_change_index = 0;

	const int APPLE = 1;
	const int SNAKE = -1;

	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };

	//방향 전환 인덱스
	//좌회전 할 경우, cur_direction = (cur_direction + 3) % 4;
	//우회전 할 경우, cur_direction = (cur_direction + 1) % 4;
	int cur_direction = 0;

	//초기 뱀 위치
	map[0][0] = SNAKE;
	pair<int, int> head = { 0, 0 };
	queue<pair<int, int>> snake;
	snake.push(head);

	cin >> n;
	cin >> k;

	for (int i = 0; i < k; i++) 
	{
		int x, y; // 사과 위치
		
		cin >> x >> y;
		map[x - 1][y - 1] = APPLE;
	}

	cin >> l;
	for (int i = 0; i < l; i++)
	{
		//방향변환
		cin >> dir_change[i].first >> dir_change[i].second;
	}

	int sec = 0;

	while (1)
	{
		sec++;

		int nx = head.first + dx[cur_direction];
		int ny = head.second + dy[cur_direction];

		if (nx < 0 || ny < 0 || nx >= n || ny >= n)
		{
			//벽이면 게임 끝
			break;
		}
		else if (map[nx][ny] == SNAKE)
		{
			//이동할 위치가 뱀의 몸의 일부분이면 게임 끝
			break;
		}
		else if (map[nx][ny] != APPLE)
		{
			//사과가 없으면 꼬리가 이동
			auto tail = snake.front();
			snake.pop();

			map[tail.first][tail.second] = 0;
		}

		//머리 한칸 이동
		head = { nx, ny };
		snake.push(head);

		map[nx][ny] = SNAKE;


		//진행 방향을 찾음
		int dir_change_sec = dir_change[cur_change_index].first;
		if (cur_change_index < l && dir_change_sec == sec)
		{
			char dir = dir_change[cur_change_index].second;
			if (dir == 'L')
			{
				cur_direction = (cur_direction + 3) % 4;
			}
			else if (dir == 'D')
			{
				cur_direction = (cur_direction + 1) % 4;
			}
			cur_change_index++;
		}
	}

	cout << sec << '\n';

	return 0;
}