뱀

 

예전 삼성전자 코딩역량테스트 문제라고한다.

 

시뮬레이션 문제고 솔직히, 문제 난이도 자체는 어렵지않았지만, 디버깅부분에서 애를 많이먹었고,

 

문제가 직관적으로 이해가 잘안된부분, 그리고 게임이 끝나는 부분에 대한 확인 미숙 등이 문제를 어렵게 느끼게 했던것같다.

 

알고리즘에 대한 생각은 시뮬레이션 문제이며,

 

뱀 자체를 벡터로 표현했는데, 헤드 부분이 벡터 0번째 인덱스며, 사과를 먹었을때 비활성화 벡터로 놓고 문제를 풀었다.

 

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>

using namespace std;

struct sn {
	int x, y;
	int dir = 0;
	bool life = false;
};

int n;
int map[102][102];
int an;
int mn;
queue<pair<int, int>> dir;
vector<sn> snake;
bool apple = false;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
bool endgame = false;
int time;

void move() {
	int x = 0; int y = 0; int d = 0;
	sn s;
	for (int i = 0; i < snake.size(); i++) {
		if (snake[i].life == true) {
			snake[i].x = snake[i].x + dx[snake[i].dir];
			snake[i].y = snake[i].y + dy[snake[i].dir];
		}
		if(snake[i].life == false ){
			snake[i].life = true;
		}
		if (snake[i].x <= 0 || snake[i].x > n || snake[i].y <= 0 || snake[i].y >n) endgame = true;
		if (i == 0)
		{
			if (map[snake[i].x][snake[i].y] == 1) {
				map[snake[i].x][snake[i].y] = 0;
				apple = true;
			}
			for (int j = 1; j < snake.size(); j++) {
				if (snake[i].x == snake[j].x && snake[i].y == snake[j].y &&snake[j].life == true)
					endgame = true;
			}
		}
	}
	if (snake.size() >= 2) {
		for (int i = snake.size() - 1; i >= 1; i--) {
			if (snake[i].dir != snake[i - 1].dir)
				snake[i].dir = snake[i - 1].dir;
		}
	}
	if (apple) {
		s.x = snake[snake.size() - 1].x;
		s.y = snake[snake.size() - 1].y;
		s.dir = snake[snake.size() - 1].dir;
		snake.push_back(s);
		apple = false;
	}
}

int main() {
	scanf("%d", &n);
	scanf("%d", &an);

	for (int i = 0; i < an; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		map[x][y] = 1;
	}
	scanf("%d", &mn);
	for (int i = 0; i < mn; i++) {
		int x,y; char s;
		scanf("%d %c", &x, &s);
		if (s == 'L') y = -1;
		if (s == 'D') y = 1;
		dir.push({ x,y });
	}
	sn first;
	first.x = 1; first.y = 1; first.dir = 0;  first.life = true;
	snake.push_back(first);
	time = 0;
	int count = 0;
	while (!endgame) {
		if (!dir.empty()) {
			if (dir.front().first == time) {
				snake[0].dir += dir.front().second;
				if (snake[0].dir == -1) snake[0].dir = 3;
				if (snake[0].dir == 4) snake[0].dir = 0;
				dir.pop();
			}
		}

		move();

		time++;
	}
	printf("%d\n", time);
	return 0;

}

 

Queue 로 (이동시간, 방향변경방향) 묶어서 담았고, while 문에서 시간이 돌때마다 그 시간에 해당하면, 머리부분의

dir을 바꿔주는 방식으로 진행했다.