[BOJ] 3190 : zmija - travelbeeee

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

---

[알고리즘풀이]

 우리가 잘 알고 있는 뱀 게임을 구현하면 됩니다.

 뱀의 머리부터 꼬리까지 상태를 저장하고 있어야되는데, 가장 처음에 입력된 값이 꼬리가 되고 가장 마지막에 입력된 값이 머리가 되므로 자료구조 queue를 이용해야합니다.

 

 1. 현재 방향에 맞춰서 머리의 위치를 움직입니다.

 2. 현재 머리의 위치가 벽 or 자신의 몸에 부딪혔는지 아닌지 체크합니다.

 3. 현재 머리의 위치에 사과가 있는지 없는지 체크합니다.

 4. 사과가 있다면 꼬리의 위치를 옮겨야되므로 queue의 가장 앞을 지웁니다.

 5. 현재 위치는 queue의 가장 뒤에 push 합니다. 

 6. 현재 시간에서 방향을 바꿔주는 명령이 있다면 바꿔줍니다.

#include<iostream>
#include<queue>
using namespace std;

// N, K, L, t1, t2, t3, t4 는 Input
// x , y 는 현재 위치
// dir은 현재 바라보는 방향
// 0 오른쪽 1 아래 2 왼쪽 3 위쪽
int N, K, L, t1, t2, t3, x, y, dir = 0;
char t4, direction[10001] = {};
// 0은 비어있음. 1은 뱀 2 는 사과
int map[101][101] = {};
// snake의 경로 저장.
queue<pair<int, int>> snake;

bool check(int a, int b) {
	// 벽이랑 자기 몸이랑 부딪치지않았으면 true
	if (0 < a && a <= N && 0 < b && b <= N && map[a][b] != 1)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		cin >> t1 >> t2;
		map[t1][t2] = 2;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> t3 >> t4;
		direction[t3] = t4;
	}
	
	int time = 0;
	snake.push(make_pair(1, 1));
	x = 1, y = 1; map[x][y] = 1;
	while (1) {
		if (dir == 0) y++;
		else if (dir == 1)
			x++;
		else if (dir == 2)
			y--;
		else
			x--;

		if (!check(x, y))
			break;
		// 기존의위치삭제
		if (map[x][y] != 2) {
			pair<int, int> temp = snake.front();
			map[temp.first][temp.second] = 0;
			snake.pop();
		}
		// 새로옮긴위치저장
		time++;
		snake.push(make_pair(x, y));
		map[x][y] = 1;
		// 방향전환
		if (direction[time] == 'D')
			dir = (dir + 1) % 4;
		else if (direction[time] == 'L') {
			dir--;
			if (dir == -1) dir = 3;
		}
	}
	cout << time + 1;
	return 0;
}

---