<Baekjoon> #3190 Simulation_뱀 c++

#3190 뱀
참고

삼성 코딩 테스트는 수리적 능력이나 아이디어를 도출해내서 문제를 해결하는 것보다 문제를 읽고 정확하게 이해하고 정확하게 구현하는 능력을 보는 것 같다. 그리고 시물레이션 문제를 많이 안 풀어보다보니 감이 잘 안 잡힌다.

✍문제 정리

• 뱀이 기어다니다가 벽또는 자기 몸과 부딪히면 게임 끝
• 뱀은 매 초마다 현재 이동중인 방향으로 이동한다
• 먼저 머리를 다음 칸에 위치시키고 이동 칸에 사과가 있다면 사과를 먹어 없애고 꼬리는 가만히 둔다. 사과가 없다면 꼬리가 있던 칸만 비워준다

💬IDEA

뱀은 매 초마다 현재 이동하는 방향으로 앞으로 가면서 머리 부분이 늘어나고, 이동한 칸에 사과가 없다면 꼬리가 위치한 칸이 줄어든다. 이를 보면 앞, 뒤 모두 push, pop연산이 가능한 deque로 구현해야 함을 알 수 있다.
deque<pair<int, int>> snake에는 현재 뱀의 머리 부분의 y,x좌표를 저장한다.

👩‍💻1. Initialize

• board상에서 사과가 있는 자리는 1, 현재 뱀의 몸통이 위치한 자리는 -1로 나타낸다
• enum { RIGHT,LEFT,DOWN,UP}로 정의하고 현재 이동 방향을 int curDir로 두어 관리한다 (처음에는 RIGHT)

👩‍💻2. Change Direction

문제에서 현재 이동 방향을 L이나 D로 바꿔주는 때가 나오는데 왼쪽으로 바꾼다고 (0, -1) , 오른쪽으로 바꾼다고 (0,1)로 바꾸어 주는 것이 아니다

void changeDir(char dir) {
	if (dir == 'L') {
		if (curDir == 0) curDir = 3;
		else if (curDir == 1) curDir = 2;
		else if (curDir == 2) curDir = 0;
		else if (curDir == 3) curDir = 1;
	}
	else if (dir == 'D') {
		if (curDir == 0) curDir = 2;
		else if (curDir == 1) curDir = 3;
		else if (curDir == 2) curDir = 1;
		else if (curDir == 3) curDir = 0;
	}
}

👩‍💻3. canMove()

매 초마다 canMove() 함수를 호출해 다음 위치로 이동할 수 있는지 없는지를 판별한다. 이동할 수 있다면 이동하고 더 이상 이동할 수 없다면 false를 return해 끝나는 시간을 출력한다

• 매 초마다 무조건 앞으로 한 칸은 이동하므로 snake의 front에 다음 위치를 push

	pair <int, int> cur = snake.front();
	int ny = cur.first + dy[curDir];
	int nx = cur.second + dx[curDir];
    snake.push_front(make_pair(ny, nx));
    board[ny][nx] = -1;

• 앞 쪽에 사과가 없다면 snake에서 꼬리를 pop하고 board 상에서 원래 있던 꼬리 부분을 0으로 만들어준다

	if (board[ny][nx] != APPLE) {
		int by = snake.back().first;
		int bx = snake.back().second;
		board[by][bx] = 0;
		snake.pop_back();
	}

👀전체코드

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

enum { RIGHT,LEFT,DOWN,UP};
const int APPLE = 1;
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };

int N;
int sec = 0;
int curDir = RIGHT;

vector<vector<int>> board;
deque <pair<int, int>> snake;

void changeDir(char dir) {
	if (dir == 'L') {
		if (curDir == 0) curDir = 3;
		else if (curDir == 1) curDir = 2;
		else if (curDir == 2) curDir = 0;
		else if (curDir == 3) curDir = 1;
	}
	else if (dir == 'D') {
		if (curDir == 0) curDir = 2;
		else if (curDir == 1) curDir = 3;
		else if (curDir == 2) curDir = 1;
		else if (curDir == 3) curDir = 0;
	}
}
bool canMove() {
	pair <int, int> cur = snake.front();
	int ny = cur.first + dy[curDir];
	int nx = cur.second + dx[curDir];

	if (ny<1 || nx<1 || ny>N || nx>N) return false;
	if (board[ny][nx] == -1) return false;

	snake.push_front(make_pair(ny, nx));
	if (board[ny][nx] != APPLE) {
		int by = snake.back().first;
		int bx = snake.back().second;
		board[by][bx] = 0;
		snake.pop_back();
	}
	board[ny][nx] = -1;
	return true;
}
int main() {
	snake.push_back(make_pair(1, 1));

	int K, L;
	cin >> N >> K;
	board = vector<vector<int>>(N + 1, vector<int>(N + 1));
	board[1][1] = -1;

	for (int i = 0; i < K; i++) {
		int y, x;
		cin >> y >> x;
		board[y][x] = APPLE;
	}

	cin >> L;
	for (int i = 0; i < L; i++) {
		int x;
		char dir;
		cin >>x>>dir; 
		while (sec != x) {
			if (!canMove()) {
				cout << sec + 1 << endl;
				return 0;
			}
			sec++;
		}
		changeDir(dir);
	}
	while (1) {
		if (!canMove()) {
			cout << sec + 1 << endl;
			return 0;
		}
		sec++;
	}
	return 0;
}