[백준] 3190번 - 뱀

링크

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

3190번: 뱀

풀이

어렸을때 했던 뱀 게임처럼 사과를 먹으면 길이가 늘어나고 꼬리나 벽에 닿으면 끝나는 그런 게임과 같은 문제이다.

 

뱀을 구성하기 위해서 deque를 이용하여 push_front를 하여 머리가 앞으로 나가는거와

                                                      pop_back를 이용하여 꼬리가 따라가는것을 구현 하였다.

 

뱀은 오른쪽과 왼쪽 두가지 방향으로만 꺾을 수있고 꺾는 조건이 없으면 직진 한다.

1. 조건이 없을때 뱀은 x축 ,y축으로만 가기에 방향에 따라서 머리가 가려고 하는 위치를 구하였고

2. 조건이 있을때 뱀이 바라보고 있는 위치에서 어디로 움직어야 조건에 맞게 움직이는 지를 구하였다.

 

뱀의 머리가 앞으로 전진 하였을때 뱀의 머리에 부딪히거나 벽에 부딪히면 종료된다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define INF 2e9
#define SIZE 101

using namespace std;

typedef long long int ll;

typedef struct Data {
	int x = 0, y = 0;
	int direct = 0;

	bool operator == (Data d) {
		return ((d.x == x) && (d.y == y));
	}
}Data;

const int brank = 0;
const int snake = 1;
const int apple = 2;

deque<Data> dq;
int board[SIZE][SIZE];
queue<pair<int, char>> query;

Data s_move(Data snake) {
	Data s_m = snake;
	if (s_m.direct == 1) {
		s_m.x += 1;
	}
	else if (s_m.direct == 2) {
		s_m.y -= 1;
	}
	else if (s_m.direct == 3) {
		s_m.x -= 1;
	}
	else if (s_m.direct == 4) {
		s_m.y += 1;
	}
	return s_m;
}

int direct_change(Data snake, char dir) {
	int s_direct = snake.direct;

	if (s_direct == 1) {
		if (dir == 'L')
			return 4;
		else
			return 2;
	}
	else if (s_direct == 2) {
		if (dir == 'L')
			return 1;
		else
			return 3;
	}
	else if (s_direct == 3) {
		if (dir == 'L')
			return 2;
		else
			return 4;
	}
	else if (s_direct == 4) {
		if (dir == 'L')
			return 3;
		else
			return 1;
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N; cin >> N;

	int K; cin >> K;
	for (int i = 0; i < K; i++) {
		int x, y; cin >> x >> y;
		board[x][y] = apple;
	}
	board[1][1] = snake;

	int L; cin >> L;
	for (int i = 0; i < L; i++) {
		int time; char m; cin >> time >> m;
		query.push({ time,m });
	}

	int s_size = 1;
	Data head; head.x = 1; head.y = 1; head.direct = 4;
	dq.push_back(head);

	int q_index = 0;
	int time=0;
	while (1){
		time++;	
		Data n_loc = s_move(dq.front());

		if (n_loc.x <= 0 || n_loc.x > N || n_loc.y <= 0 || n_loc.y > N) {
			break;
		}
		if (board[n_loc.x][n_loc.y] == apple) {
			dq.push_front(n_loc);
			board[n_loc.x][n_loc.y] = snake;
		}
		else if (board[n_loc.x][n_loc.y] == brank) {
			board[n_loc.x][n_loc.y] = snake;
			dq.push_front(n_loc);

			board[dq.back().x][dq.back().y] = brank;
			dq.pop_back();
		}
		else if (board[n_loc.x][n_loc.y] == snake) {
			break;
		}

		if (!query.empty()) {
			if (query.front().first == time) {
				dq.front().direct = direct_change(dq.front(), query.front().second);
				query.pop();
			}
		}
	}

	cout << time;;
	 
}