백준 3190 뱀

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

3190번: 뱀

삼성 SW 역량 테스트 기출 위주로 먼저 풀고 있는데 생각보다 구현 문제가 많다? 라는 생각이 든다

 

이번 문제는 Dummy 라는 도스게임에서 따온 문제로 규칙이 간단하다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다

해당 규칙들을 보니 문제를 해결하기 위해서는

1. 뱀의 위치를 기록

2. 뱀의 머리를 이동해서 매초마다 갱신

3. 뱀의 꼬리의 위치를 계속 기록하거나 얻을 수 있어햐한다.

머리와 뱀이 배열에서 차지하는 부분을 갱신하는 부분은 자료구조를 사용하지 않아도 구현 가능하지만

꼬리의 위치를 알기 위해서는 큐의 FIFO 성질을 이용하면 구현이 간편할 것 같았다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <utility>
#include <queue>

using namespace std;


typedef struct route {
	int x; int y;
};

int n, k, l;
int board[101][101] = {0, };
int rotate_info[100][2];

int dir[4][2] = {
	{0, +1}, {+1, 0}, {0, -1}, {-1, 0}
};

queue<route> snake;

int main(void) {

	int i;
	int a, b;
	char r;

	scanf("%d", &n);
	//getchar();
	scanf("%d", &k);
	//getchar();
	for (i = 0; i < k; i++) {
		scanf("%d %d", &a, &b);
		board[a][b] = 1; // apple
	}

	scanf("%d", &l);
	//getchar();

	for (i = 0; i < l; i++) {
		scanf("%d %c", &rotate_info[i][0], &rotate_info[i][1]);
	}

	int time = 0, x = 0, flag = 0, rotate_idx = 0;
	int head_x = 1, head_y = 1;
	int tail_x = 1, tail_y = 1;

	route head, tail;

	board[1][1] = 2; // snake
	head.x = 1; head.y = 1;
	snake.push(head);

	while (1) {

		head_x += dir[x][0]; head_y += dir[x][1];
		time++;
		// collision check
		if (board[head_x][head_y] == 2 || head_x == 0 || head_x == n+1 || head_y == 0 || head_y == n+1) {
			break;
		}
		// check snake ate apple or not
		if (board[head_x][head_y] == 1) {
			flag = 1;
		}
		else flag = 0;
		
		board[head_x][head_y] = 2;
		head.x = head_x; head.y = head_y;
		snake.push(head);

		tail = snake.front();

		if (!flag) {
			// upadte tail -> need to know direction
			board[tail.x][tail.y] = 0;
			snake.pop();
		}

		if (rotate_idx < l && time == rotate_info[rotate_idx][0]) {
			if (rotate_info[rotate_idx][1] == 'D') {
				x++;
			}
			else {
				x--;
			}
			rotate_idx++;
			if (x == 4) x = 0;
			if (x == -1) x = 3;
		}

	}

	printf("%d", time);

	return 0;
}