3190 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

문제의 조건에 맞춰 구현하는 구현 문제이다. 어려운 부분은 없었지만, 실수하는 부분들이 있어 시간을 잡아먹었다.

먼저, 뱀의 이동과 비슷한 동작을 하는 자료구조인 덱(deque)을 사용하여 표현했는데, 앞, 뒤로 넣고 빼는게 비슷하다.

유의해야할 조건은 다음과 같다.

1. 다음 칸에 사과가 있다면, 덱을 push_front만 한다.

2. 다음 칸에 사과가 없다면, 덱을 push_front, pop_back한다. 이 때, 뱀의 몸통을 표현하기 위해 보드에 1로 저장해놓는다

3. 다음 칸이 보드의 끝이거나 뱀의 몸통이라면 종료한다.

 

또한 뱀의 이동방향도 구현해줘야 하는데, 방향 변수를 따로 선언하여 90도 회전을 표현하기 위해 덧셈과 모듈러(%) 연산을 사용했다.

예를 들어, 방향 값 0, 1, 2, 3을 각각 우, 상, 좌, 하로 가정한다면

왼쪽으로 90도 회전하기 : 방향 값에 1을 더하여 %연산을 한다.

오른쪽으로 90도 회전하기 : 방향 값에 3을 더하여 %연산을 한다.

구현 문제에서 자주 등장하는 방향은 %연산을 이용하여 구현하면 코드의 양을 줄일 수 있어 편하다.

 

마지막으로 queue를 사용하여 뱀의 이동방향을 구현해주었는데, 시간에 따라 방향이 변하는게 큐와 비슷하기 때문이다.

 

나의 경우 실수한 부분은 (0, 0)에서 시작한다고 오해했었는데, 문제의 조건에 (1, 1)에서 시작하는걸 뒤늦게 확인하여 디버깅하느라 시간이 걸렸다.

 

정답코드

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
int N, L;
int BoardSize;
int board[101][101];
queue<pair<int, char>> q;
deque<pair<int, int>> snake;
//오른쪽 +3, 왼 +1
pair<int, int> nextPos(int dir, int row, int col)
{
	switch (dir) {
	case 0://오른
		return { row, col + 1 };
	case 1://위
		return { row - 1, col };
	case 2: //왼
		return { row, col - 1 };
	case 3: //아래
		return { row + 1, col };
	}
}
int PlayGame()
{
	int time = 0, dir = 0;
	char d;
	int nr, nc;
	board[1][1] = 1;
	snake.push_back({ 1, 1 });
	while (1) {
		time++;
		pair<int, int> next = nextPos(dir, snake.front().first, snake.front().second);
		nr = next.first;
		nc = next.second;
		if (board[nr][nc] == 2)
			snake.push_front({ nr, nc });
		else if (board[nr][nc] == 1)
			break;
		else if (nr <= 0 || nc <= 0 || nr > BoardSize || nc > BoardSize)
			break;
		else {
			snake.push_front({ nr, nc });
			board[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}
		board[nr][nc] = 1;

		if (!q.empty() && time == q.front().first) {
			if (q.front().second == 'D') //오른
				dir = (dir + 3) % 4;
			else if (q.front().second == 'L') //왼
				dir = (dir + 1) % 4;
			q.pop();
		}
	}
	return time;
}
int main()
{
	cin >> BoardSize;
	int apple, row, col;
	cin >> apple;
	for (int i = 0; i < apple; i++) {
		cin >> row >> col;
		board[row][col] = 2;
	}
	cin >> L;
	int time, answer;
	char dir;
	for (int i = 0; i < L; i++) {
		cin >> time >> dir;
		q.push({ time, dir });
	}
	answer = PlayGame();
	printf("%d\n", answer);
	return 0;
}