BOJ 3190: 뱀

#BOJ 3190: 뱀

3190번: 뱀

#풀이

1. 뱀은 사과를 먹으면 몸의 길이가 증가함

2. 뱀은 오른쪽,왼쪽으로 90도 방향 회전이 가능함

3. 뱀은 정사각형을 나가거나 자신의 몸에 닿으면 게임이 끝남

 

이 조건을 해결하면 풀 수 있는 문제이다. 근데 이거 문제가 너무 정보가 부족하게 나온다.

내가 이게임을 제대로 안해봐서 그런가...??

 정사각형 외곽에 벽이 있다고 했는데 이게 정사각형을 나갔을 때 인지 아니면 그냥 배열의 외곽에 위치하면 끝나는 건지 헷갈렸다. 이유는 나갔을 때와 외곽에 위치할 때 답의 차이가 1 있기 때문이다.....

 또한 뱀이 사과가 없는 칸을 이동 했을 때 뱀의 머리가 이동하면서 vector맨 앞 요소에 추가를 하고 맨 마지막 원소를 제거 하면 뱀의 이동을 나타낼 수 있는데 조건 3에 자신의 몸에 닿으면 게임이 끝난다고 되어있다... 사과를 먹지 않는 이상 뱀의 크기가 늘어나지 않으므로 이동을 하면 머리와 꼬리가 동시에 앞으로 가므로 닿을 수 없다고 생각했는데 예제 3번을 보면서 뱀의 머리가 먼저 이동하고 이동 했을 때 꼬리가 닿으면 게임이 끝나야 예제 3번의 답이 나올 수 있었다.... 

간단하게 구현할 수 있다.

 

#코드

#include<iostream> // #include<bits/stdc++.h>
#include<queue>
using namespace std;
int board[100][100];
int n, k, l;
int location = 1; // 0 상, 1 우, 2,하, 3좌
vector<pair<int, int>> v; // 뱀
queue<pair<int, char>> Q;
int ans;
void func() {
	v.push_back({ 0, 0 });
	while (true) {
		auto a = v[0];
		if (!Q.empty())
		{
			auto b = Q.front();
			if (b.first == ans) {
				Q.pop();
				if (b.second == 'D') { // 오른쪽 90도
					location = location == 3 ? 0 : location + 1;
				}
				if(b.second =='L') { // 왼쪽 90 도
					location = location == 0 ? 3 : location - 1;
				}
			}
		}
		int x = 0;
		int y = 0;
		if (location == 0) { // 방향전환
			x = a.first - 1;
			y = a.second;
		}
		else if (location == 1) {
			x = a.first;
			y = a.second + 1;
		}
		else if (location == 2) {
			x = a.first + 1;
			y = a.second;
		}
		else {
			x = a.first;
			y = a.second - 1;
		}

		if (x < 0 || y < 0 || x >= n || y >= n) {
			ans++;
			return;
		}
		v.insert(v.begin(), { x, y });
		ans++;	
		for (int i = 0; i < v.size() - 1; i++) { // 뱀머리가 몸에 닿았느지 확인
			for (int j = i + 1; j < v.size(); j++) {
				if (v[i] == v[j]) {
					return;
				}
			}
		}
		if (board[x][y] != 2) // 뱀 이동
			v.erase(v.end() - 1);
		else {
			board[x][y] = 0;
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		board[x-1][y-1] = 2;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		int s;
		char c;
		cin >> s >> c;
		Q.push({ s, c });
	}
	func();
	cout << ans << '\n';
	return 0;
}