[백준] 3190 뱀

[백준 3190] 뱀

<풀이 과정>
1.(0,0)에서 시작하여 우측으로 진행하고 시간은 1초부터 시작한다.
2. 현 위치에서 이동할 방향으로 머리를 1칸 이동
2-1. 이때 이동할 수 있는 위치(map 혹은 사과)라면 이동한다.
3. 이동한 자리가 사과가 아니면 꼬리를 당겨준다
(꼬리가 있었던 위치를 0으로 바꿔주고 큐에서 제거)
4. 현재 경과 시간에 방향 전환 값이 있다면 방향을 바꿔준다.
5. 머리의 위치를 snake(-1)로 바꿔주고 큐에 좌표 삽입

이 과정을 이동이 불가능 한 상태일 때 까지 반복한 뒤 총 시간 출력

#include <iostream>
#include <queue>
#include <vector>
#define SNAKE -1
#define APPLE 1
using namespace std;

int N, K, L;
int map[100][100]; 
int time; //경과 시간
char turn[10001]; //회전 정보
int d[] = { 0,1 }; //이동 방향
int head[2]; //머리 위치, 초기는 0,0

bool IsMove(int dx, int dy);
void ChangeDir(int &dx, int &dy, char &dir);

int main() {
	scanf("%d", &N);
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		int ax, ay;
		scanf("%d %d", &ax, &ay);
		map[ax - 1][ay - 1] = APPLE;
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		int a, b;
		scanf("%d %c", &a, &b);
		turn[a] = b; //a초에 b방향으로 회전
	}

	map[0][0] = SNAKE;
	queue<pair<int, int>> snake; //뱀의 궤적 정보
	snake.push(make_pair(0, 0));

	
	//(0,0)에서 시작하여 우측으로 진행, 시간은 1초부터 시작
	//1) 현 위치에서 이동할 방향으로 머리를 1칸 이동
	//2) 이때 이동할 수 있는 위치(map의 빈칸 or 사과) 라면 이동
	//2-1) 이동이 불가능(map을 넘어가거나 자기 몸과 닿으면) 종료
	//3) 이동한 자리가 사과가 아니면 꼬리를 당겨줌(꼬리 위치를 0으로)
	//4)현재 경과 시간에 방향전환 값이 있다면 방향을 바꿈(현재 x초가 끝난 후에)
	//5)머리의 위치 값을 SNAKE(-1)로 바꿔주고 queue에 좌표 삽입
	//3,4, 과정을 이동이 불가능한 상태일 때 까지 반복한 뒤 총 시간 출력
	
	for (time = 1;; time++) {
		int dx = head[0] + d[0];
		int dy = head[1] + d[1];
		//처음에는 오른쪽으로 이동
		if (!IsMove(dx, dy)) break;//이동이 불가능 하면 종료

		head[0] = dx;
		head[1] = dy;

		//3)이동한 자리가 사과가 아니면 꼬리를 당겨줌
		if (map[dx][dy] != APPLE) {
			pair<int, int> tail = snake.front();
			map[tail.first][tail.second] = 0;
			snake.pop();
		}
		//4)방향 전환 값이 있다면 방향 바꾸기
		if (turn[time]) ChangeDir(d[0], d[1], turn[time]);

		//5) 머리의 위치 값을 -1로 바꿔주고 큐에 삽입
		map[dx][dy] = SNAKE;
		snake.push(make_pair(dx, dy));
	}
	
	cout << time << '\n';

	return 0;
}

bool IsMove(int dx, int dy) {
	//맵 내부이거나 자기 자신에 닿지 않을 경우 이동 가능 
	return ((dx >= 0 && dx < N) && (dy >= 0 && dy < N)) && map[dx][dy] != SNAKE;
}

void ChangeDir(int &dx, int &dy, char &dir) {
	if (dx == 0 && dy == 1) { //오른쪽 방향
		if (dir == 'D') {
			dx = 1;
			dy = 0;
		}
		else {
			dx = -1;
			dy = 0;
		}
	}

	else if (dx==0 && dy==-1) { //왼쪽 방향
		if (dir == 'D') {
			dx = -1;
			dy = 0;
		}
		else {
			dx = 1;
			dy = 0;
		}
	}
	else if (dx == 1 && dy == 0) {//아럐쪽 방향
		if (dir == 'D') {
			dx = 0;
			dy = -1;
		}
		else {
			dx = 0;
			dy = 1;
		}
	}
	else if (dx == -1 && dy == 0) {//위쪽 방향
		if (dir == 'D') {
			dx = 0;
			dy = 1;
		}
		else {
			dx = 0;
			dy = -1;
		}
	}
}