[BOJ] 3190번_뱀_덱 (C++)

[문제]

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

뱀이 나와서 기어다니는데, 사과를 먹으면 뱀의 길이가 늘어나는 게임이 있다. 뱀이 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 N*N 정사각형 보드에서 진행되고 몇몇 칸에는 사과가 놓여져 있다. 게임이 시작할 때 뱀은 (1,1)에서 시작하며 길이는 1이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동하는데 아래의 규칙을 따른다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하는 문제이다.

[사용 알고리즘]

덱

[풀이 핵심]

• deque를 이용해서 뱀의 위치를 저장해주고 덱의 front()를 머리, back()을 꼬리로 생각하고 풀었다.
• graph 배열에 게임이 진행되고 있는 보드의 상황을 저장해주면서 다음칸이 벽인지, 뱀의 몸인지, 그냥 비어있는 길인지, 사과인지에 따라 조건에 맞는 처리를 해줬다.
• 뱀의 회전 처리는 입력받은 int,char값을 pair<int,char>로 이루어진 queue에 저장해놨다가 입력받은 시간이 되면 회전처리를 해주고 q를 pop해주는 방식으로 해결했다.

[코드]

//boj3190번_뱀_자료구조(덱)

#include<iostream>
#include<deque>
#include<queue>

using namespace std;

int graph[101][101];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int N;
	cin >> N;

	int K;
	cin >> K;

	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;

		graph[x][y] = 2;
	}

	int L;
	cin >> L;

	queue<pair<int, char>> q;

	for (int i = 0; i < L; i++) {
		int X;
		char C;
		cin >> X >> C;

		q.push({ X,C });
	}

	graph[1][1] = 1;

	deque<pair<int, int>> d;
	d.push_back({ 1,1 });

	int dir = 0;

	int time = 0;

	while (true) {
		time++;
		
		int next_x = d.front().first + dx[dir];
		int next_y = d.front().second + dy[dir];

		if (next_x <= 0 || next_x > N || next_y <= 0 || next_y > N) {
			cout << time;
			return 0;
		}
		else if (graph[next_x][next_y] == 0) {
			graph[next_x][next_y] = 1;
			d.push_front({ next_x,next_y });

			graph[d.back().first][d.back().second] = 0;
			d.pop_back();
		}
		else if (graph[next_x][next_y] == 1) {
			cout << time;
			return 0;
		}
		else if (graph[next_x][next_y] == 2) {
			graph[next_x][next_y] = 1;
			d.push_front({ next_x,next_y });
		}

		if (!q.empty()) {
			if (q.front().first == time) {
				if (q.front().second == 'D') {
					dir = (dir + 1) % 4;
				}
				else if (q.front().second == 'L') {
					dir = (dir + 3) % 4;
				}
				q.pop();
			}
		}
	}

	return 0;
}