3190_뱀

▶골드4

풀이

사과를 먹은 개수에 맞는 몸길이 유지, 방향 전환, 조건 만족 여부가 관건인 문제이다.

먼저 현재 방향에 맞게 앞으로 한 칸 전진 한 후, 

그 자리에 사과가 존재하면 그대로, 존재하지 않으면 꼬리를 제거한다.

그리고 방향 전환 시간이 되었을 시, D일 경우 우회전, L일 경우 좌회전을 한다.

 

필요한 자료구조로는,

① 현재 방향을 나타내는 방향 배열(x, y 두 개)

② 방향 전환 queue(시간과 방향 두 개를 받음)

③ 뱀 몸 인덱스 queue(x, y 두 개)

④ 뱀이 지나간 여부를 나타내는 2차원 배열

⑤ 사과가 존재하는 여부를 나타내는 2차원 배열

 

먼저 입력을 받고 적절한 자료구조에 데이터를 넣어준다.

현재 x위치, y위치에 현재 방향에 맞게 1칸 전진한 값을 더해준다.

그 자리에 사과가 존재하지 않을 경우 꼬리 칸에 해당하는 x, y 인덱스 배열을 false로 바꾸어주고

사과가 존재할 경우 사과 칸의 해당 x, y 인덱스 배열을 false로 바꾸어준다.

다음으로, 방향 전환 시간과 일치하는지 확인 후 일치하고 방향이 'D'이면 우회전, 방향이 'L'이면 좌회전한다.

그리고 방향 전환 queue를 pop한다.

 

코드

#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

//오, 아, 왼, 위
int x[4] = { 0, 1, 0, -1 };
int y[4] = { 1, 0, -1, 0 };

//방향 전환 queue
queue <pair <int, char>> direc;
//뱀 위치 queue
queue <pair <int, int>> snake;

int n, k;
int ans = 0;

//뱀이 지나간 여부
bool map[102][102];
//사과 존재 여부
bool apple[102][102];

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

	cin >> n >> k;

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

	int L;
	cin >> L;
	for (int i = 0; i < L; i++) {
		int c;
		char d;
		cin >> c >> d;
		direc.push({ c, d });
	}
	int chnT = direc.front().first;
	int chnD = direc.front().second;

	int nowX = 1, nowY = 1, nowD = 0;
	map[1][1] = true;
	snake.push({ 1, 1 });

	while (1) {

		nowX += x[nowD];
		nowY += y[nowD];

		//현재 방향으로 한 칸 전진
		if (nowX <= n && nowX > 0 && nowY <= n && nowY > 0 && map[nowX][nowY] == false) {
			snake.push({ nowX, nowY });
			map[nowX][nowY] = true;
			//해당 자리에 사과가 없을 경우
			if (apple[nowX][nowY] == false) {
				map[snake.front().first][snake.front().second] = false;
				snake.pop();
			}
			else {
				apple[nowX][nowY] = false;
			}
		}
		//벽이나 자기 몸에 부딫히는 경우
		else {
			cout << ans + 1 << endl;
			return 0;
		}

		//방향 바꾸는 시간이면 바꾸기 & 시간 갱신
		if (++ans == chnT) {
			//우회전
			if (chnD == 'D' && nowD != 3) {
				nowD++;
			}
			else if (chnD == 'D' && nowD == 3) {
				nowD = 0;
			}
			//좌회전
			else if (chnD == 'L' && nowD != 0) {
				nowD--;
			}
			else {
				nowD = 3;
			}
			direc.pop();
			if (!direc.empty()) {
				
				chnT = direc.front().first;
				chnD = direc.front().second;
			}
		}
	}
	cout << ans + 1 << endl;
}