[BOJ] #3190 _ 뱀

[뱀] https://www.acmicpc.net/problem/3190

3190번: 뱀

시뮬레이션 문제이다.

알려준 규칙대로 코드를 구현하면 된다.

 

이동한 칸에 사과가 없을 경우, 꼬리가 위치한 칸을 비워주는 것이 관건이다.

이는 선입선출인 큐를 이용하여 구현하였다. (end: 머리, front: 꼬리)

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 101

using namespace std;

int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1,  0, -1 };
int map[MAX][MAX];
int n;
queue<pair<int, int> > mv;

int solve();
int main() {
	int r, c, apple, l, x;
	char C;

	scanf("%d", &n);
	scanf("%d", &apple);
	for (int i = 0; i < apple; i++) {
		scanf("%d %d", &r, &c);
		map[r][c] = 1; //apple : 1
	}
	scanf("%d", &l);
	while (l--) {
		scanf("%d %c", &x, &C);
		if(C == 'D') mv.push(make_pair(x, 1));
		else mv.push(make_pair(x, -1));
	}

	printf("%d\n", solve());

	return 0;
}

int solve() {
	int time = 1, d = 0, r, c;
	queue<pair<int, int> > snake;
	snake.push(make_pair(1, 1));
	map[1][1] = 2;

	while (1) {
		r = snake.back().first + dy[d];
		c = snake.back().second + dx[d];

		if (mv.size() > 0) {
			if (time == mv.front().first) {
				d += mv.front().second;
				if (d < 0) d = 3;
				else if (d > 3) d = 0;
				mv.pop();
			}
		}

		if (r<1 || c<1 || r>n || c>n) break;
		if (map[r][c] == 2) break;
		if (map[r][c] == 0) {
			map[snake.front().first][snake.front().second] = 0;
			snake.pop();
		}
		map[r][c] = 2; //snake : 2
		snake.push(make_pair(r, c));
		time++;
	}

	return time;
}