백준 3190: 뱀

문제 요약

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
  
  사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

문제 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

문제 풀이

맵을 2차원 배열로 만들어서 뱀은 1, 사과는 2, 그 외는 0으로 매칭시켜서 그렸다.

뱀의 머리부터 꼬리까지의 위치를 list<pair<int,int>>로 저장하여

이동시 pop_front(), push_back()을 하고, 사과가 있을 시에는 pop_front()를 하지 않도록 하였다.

방향 전환 정보를 queue<pair<int,char>>로 저장하여 선입 순서대로 처리하도록 하였다.

현재 시간을 cnt에 할당하여 이동할때마다 cnt++, 도착한 곳의 정보에 따라 게임을 끝내거나 하는 등 옵션을 추가하였다.

현재의 방향이 오른쪽, 아래, 왼쪽, 위 중 어디를 향하고있는지 담는 state변수도 만들어서,

방향을 'D', 즉 뱀이 머리를 우측으로 돌릴 경우 state++, 'L'의 왼쪽으로 변경할 경우 state--를 해서 방향전환을 했고 0, 1, 2, 3을 각 오른쪽, 아래, 왼쪽, 위의 방향으로 매치하였다. 당연히 state가 음수 혹은 4이상이 되지 않도록 연산처리도 해주었다.

task가 전부 비어서 while문을 빠져나왔을 때는 현재의 방향(state)대로 쭉 나아가게 하는 코드까지 넣어주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>

using namespace std;

int map[102][102] = { 0, };

int main()
{
	list<pair<int, int>> snake;
	queue<pair<int, char>> task;
	pair<int, int> f, temp, temp2;
	int n, k, l, in1, in2, cnt = 0;
	bool end = false;
	char in3;
	int state = 0;	// 오: 0, 아래: 1, 왼: 2, 위:3
	cin >> n;
	cin >> k;
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &in1, &in2);
		map[in1][in2] = 2;	// 2가 사과
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		scanf("%d %c", &in1, &in3);
		task.push({ in1, in3 });
	}
	snake.push_back({ 1,1 });
	map[1][1] = 1;
	while (!task.empty() && !end) {
		f = task.front();
		while (cnt < f.first) {
			cnt++;
			temp = snake.front();	// 꼬리
			temp2 = snake.back();	// 머리
			if (state == 0)
				temp2.second++;
			else if (state == 1)
				temp2.first++;
			else if (state == 2)
				temp2.second--;
			else
				temp2.first--;

			if (temp2.first <= 0 || temp2.second <= 0 || temp2.first > n || temp2.second > n
				|| map[temp2.first][temp2.second] == 1)	// 벽 혹은 몸통에 부딫혔다?
			{
				end = true;
				break;
			}
			else if (map[temp2.first][temp2.second] == 2)	// 사과다?
			{}
			else {
				map[temp.first][temp.second] = 0;
				snake.pop_front();
			}
			map[temp2.first][temp2.second] = 1;
			snake.push_back(temp2);
		}
		if (f.second == 'D') state = (state + 1) % 4;
		else {
			state--;
			if (state < 0) state = 3;
		}
		if (end) break;
		task.pop();
	}
	if (task.empty()) {
		while (true) {
			cnt++;
			temp = snake.front();	// 꼬리
			temp2 = snake.back();	// 머리
			if (state == 0)
				temp2.second++;
			else if (state == 1)
				temp2.first++;
			else if (state == 2)
				temp2.second--;
			else
				temp2.first--;

			if (temp2.first <= 0 || temp2.second <= 0 || temp2.first > n || temp2.second > n
				|| map[temp2.first][temp2.second] == 1)	// 벽 혹은 몸통에 부딫혔다?
				break;
			else if (map[temp2.first][temp2.second] == 2)	// 사과다?
			{}
			else {
				map[temp.first][temp.second] = 0;
				snake.pop_front();
			}
			map[temp2.first][temp2.second] = 1;
			snake.push_back(temp2);
		}
	}
	cout << cnt;
	return 0;
}