BOJ-3190 뱀

필요한 지식

1. 시뮬레이션

2. Deque

접근

1. 머리는 항상 1칸씩 이동하지만, 사과의 먹냐 안먹냐에따라 꼬리가 제자리에있거나 이동한다. 머리와 꼬리에 둘다 접근이 가능해야한다.

2. 뱀이 자기 몸에 박거나 벽에 박으면 게임이 종료된다. 자기 몸에 박는경우를 찾아줘야하므로 뱀의 몸 좌표들을 가지고있어야한다.

• 머리와 꼬리 둘다 접근이 가능하며, 몸의 좌표들에 접근이 가능해야하므로 Deque를 사용했다.

• 뱀의 머리는 방향을 가지고 있으므로 좌표를 나타내기위한 point 구조체에 앞으로의 진행방향을 나타내는 변수 d를 추가했다.

• d는 0~4의 값을 가지고 0부터 우,하,상,좌 의 방향을 나타낸다.

• 뱀이 1번 이동할때 머리의 d변수만 보고 dir배열에 접근해서 이동시키켜주면된다.

• 사과를 먹으면 없애줘야한다.

코드(C++)

#include <iostream>
#include <deque>
#include <string>
using namespace std;
int arr[101][101], dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }, n, k, l, x, t = 0;
string c;
typedef struct point {
	int y, x, d;
};
deque<point>dq;
bool move() {
	point next = dq.back();
	next.y += dir[next.d][0]; next.x += dir[next.d][1];
	if (0 < next.y && next.y <= n && 0 < next.x && next.x <= n) {
		for (auto it : dq) if (it.y == next.y && it.x == next.x) return false;
		if (!arr[next.y][next.x]) dq.pop_front();
		else arr[next.y][next.x] = 0;
		dq.push_back(next);
		return true;
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	dq.push_back(point{ 1,1,0 });
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b; cin >> a >> b; arr[a][b] = 1;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		cin >> x >> c;
		while (x > t) {
			t++;
			if (!move()) {
				cout << t;
				return 0;
			}
		}
		if (c == "D") {
			dq.back().d += 1;
			if (dq.back().d >= 4) dq.back().d -= 4;
		}
		else {
			dq.back().d -= 1;
			if (dq.back().d < 0) dq.back().d += 4;
		}
	}
	do {
		t++;
	} while (move());
	cout << t;
	return 0;
}