[백준 3190] 뱀

문제 링크 => 3190번: 뱀 (acmicpc.net)

3190번: 뱀

---

Deque 를 이용하는 문제이다.

 

뱀의 초기 위치를 (1, 1), 방향은 오른쪽이라고 주어졌고, 사과를 먹으면 뱀의 길이가 증가하고 먹지 못하면 뱀의 길이는 그대로이다.

 

뱀의 머리 부분과 꼬리 부분을 Deque 의 front, back 이라고 두고 사과를 먹은 경우와 안 먹은 경우를 살펴보도록 한다.

 

사과를 먹은 경우 ) front 에 뱀이 다음으로 이동할 위치(nextX, nextY) 를 push 해주고 front 를 제외한 나머지 부분(front + 1 ~ back) 에 대해서 이동할 위치(nextX, nextY) 와 동일한 경우 게임이 종료되고 아닌 경우 게임을 계속 진행하도록 한다. 

그리고 사과를 먹은 경우 해당 위치에 사과가 없도록 표시해줘야 한다. ( apple[x][y] = true 인 경우 false 로 변경 )

 

사과를 먹지 않은 경우 ) 사과를 먹은 경우와 동일하게 front 에 뱀이 다음으로 이동할 위치(nextX, nextY) 를 push 해주고 front 를 제외한 나머지 부분(front + 1 ~ back) 에 대해서 이동할 위치(nextX, nextY) 와 동일한 경우 게임이 종료되고 아닌 경우 꼬리 부분이 이동해야 하므로 꼬리 부분을 pop 해준다.

 

위 과정을 반복하면서 범위를 벗어나거나 뱀이 자기자신의 몸을 부딪히는 경우 게임이 종료된다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, K, L, direction;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool apple[101][101];
queue<pair<int, char>> Q;
deque<pair<int, int>> snakeDq;

void input() {

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

	cin >> L;
	for (int i = 0; i < L; i++) {
		int x;
		char c;
		cin >> x >> c;
		Q.push({ x,c });
	}

	snakeDq.push_front({ 1,1 });
	direction = 1;
}


void solve() {

	int Time = 0;
	while (1) {
		if (Q.size() && Time == Q.front().first) {
			if (Q.front().second == 'L') direction = (direction + 3) % 4;
			else direction = (direction + 1) % 4;
			Q.pop();
		}
		Time++;

		int x = snakeDq.front().first, y = snakeDq.front().second;
		x += dx[direction], y += dy[direction];		
		if (x == 0 || x > N || y == 0 || y > N) break;
		snakeDq.push_front({ x,y });

		pair<int, int> front = snakeDq.front();
		snakeDq.pop_front();
		snakeDq.push_back(front);

		int dqSize = snakeDq.size(), op = 1;
		for (int i = 0; i < dqSize - 1; i++) {
			pair<int, int> p = snakeDq.front();
			if (front.first == p.first && front.second == p.second) op = 0;
			snakeDq.pop_front();
			snakeDq.push_back(p);
		}
		if (op == 0) break;
		
		if (!apple[x][y]) snakeDq.pop_back();
		else apple[x][y] = false;
	}

	cout << Time;

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}