백준 3190 뱀

문제 : https://www.acmicpc.net/workbook/view/1152

 

서론

시뮬레이션 문제이며 큐를 활용했다.

 

---

풀이

입력받으면서 회전은 큐에 저장하고 사과는 지도에 표시한다.

그리고 문제에 적혀진 매 초가 지날때마다 일어나는 행위들을 반복문에 쓴다.

 

뱀은 큐에도 저장하고 지도에도 위치를 표시했는데, 큐에 저장한것은 꼬리를 제거하기 위함이고 지도에 표시한건 자기 몸과 부딫히거나 벽과 닿는지 확인하기 위해서다. 

int dy[4] = { 0, 1, 0, -1 }; // 우하좌상
int dx[4] = { 1, 0, -1, 0 };
while (++time) {

	// 이동방향으로 한칸 이동
	y = y + dy[dir];
	x = x + dx[dir]; 

	// 자기 몸과 부딫히거나 벽과 닿으면 끝
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 1) break;

	
	if (map[y][x] != -1) { // 현재 위치에 사과가 없으면
		map[snake.front().y][snake.front().x] = 0; // 꼬리를 자름
		snake.pop(); // 마찬가지로 꼬리를 자름
	}
	map[y][x] = 1; // 현재 위치에 머리 위치
	snake.push({ y, x }); // 마찬가지로 머리 위치

	if (!rot.empty() && rot.front().time == time) { // 회전할 시간이 되면
		if (rot.front().dir == 'L') { // 왼쪽이면 왼쪽으로 회전
			dir--;
			if (dir == -1) dir = 3;
		}
		else dir = (dir + 1) % 4; // 오른쪽이면 오른쪽으로 회전
		rot.pop();
	}
}

 

---

구현

// c++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n;
int k;
int l;

int map[100][100];
int dy[4] = { 0, 1, 0, -1 }; // 우하좌상
int dx[4] = { 1, 0, -1, 0 };
queue<pair<int, int>>rot;
queue <pair<int, int>>snake;

void init() {
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int y, x;
		cin >> y >> x;
		map[y-1][x-1] = -1; // 사과는 -1
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		int x;
		char c;
		cin >> x >> c;
		if (c == 'L') rot.push({ x, -1 });
		else if(c == 'D') rot.push({ x, 1 });
	}
}



int main() {
	init();

	int time = 0;
	int dir = 0;
	int y = 0;
	int x = 0;
	map[y][x] = 1;
	snake.push({ y, x });
	while (++time) {

		y = y + dy[dir];
		x = x + dx[dir];

		//cout << y << " " << x << " " << time << endl;

		if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 1) break;

		if (map[y][x] != -1) { 
			map[snake.front().first][snake.front().second] = 0;
			snake.pop(); 
		}
		map[y][x] = 1;
		snake.push({ y, x });
		
		if (!rot.empty() && rot.front().first == time) {
			if (rot.front().second == -1) {
				dir--;
				if (dir == -1) dir = 3;
			}
			else dir = (dir + 1) % 4;
			rot.pop();
		}
	}

	cout << time;
}