[백준 3190] 뱀 (C++)

풀이

뱀이 이동할 때를 생각해보자.

이동할 때 머리를 쭉 늘려 전진하고 뒤의 꼬리를 땡겨온다.

자료구조 deque 를 사용하면 편하게 구현할 수 있다. (앞 뒤로 땡기거나 늘릴 수 있기 때문)

 

뱀이 이동하기 때문에 1초가 소요된다.

아래의 로직들은 1초 동안에 수행되는 행동들이다.

뱀이 움직이는 방향을 아래와 같이 정의할 수 있다.

dir = 0 오른쪽
dir = 1 아래쪽
dir = 2 왼쪽
dir = 3 위쪽

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

dir 방향대로 움직인다고 했을 때 다음칸을 확인해보고 움직임을 결정하면 된다.

 

사과가 있는 칸인 경우

해당 칸을 먹었다고 표시해주고, 뱀의 머리를 늘려주면 된다.

이때 꼬리는 자르지 않는다.

 

사과가 없는 칸인 경우

해당 칸에 아무것도 없으므로 뱀의 머리를 늘려주고 꼬리를 잘라준다.

뱀이 이동할 때를 생각하면 머리를 쭉 앞으로 늘리고 뒤에 꼬리를 땡기는 방식을 상상하면 이해하기 쉽다.

 

해당 칸이 벽이거나 자신의 몸통인 경우

벽인지 아닌지는 해당 좌표가 범위를 벗어났는지를 체크하면 되고

자신의 몸통인지 확인하는 방법은 deque 를 순회하면서 그 좌표와 일치하는 좌표가 있다면 몸통과 부딪힌 경우고

없다면 이동이 가능하다.

bool isValid(int nx, int ny)
{
	// 벽이거나
	if (nx <= 0 || ny <= 0 || nx > N || ny > N) return false;

	// 자신이면
	for (int i = 0; i < dq.size(); i++)
	{
		if (nx == dq[i].first && ny == dq[i].second)
			return false;
	}

	return true;
}

 

특정 시간에 방향을 변환하는 경우

뱀이 이동한 후에 시간을 보니 방향을 바꾸라는 시간과 일치한다면 방향을 바꿔주자.

방향을 자세히 보면 규칙이 있는데 규칙은 다음과 같다.

'D'인 경우
dir = (dir + 1) % 4;

'L'인 경우
dir = (dir + 3) % 4;

 

이제 기능들을 조합해서 문제를 해결하면 아래와 같다.

 

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

// 0 우, 1 하, 2 좌, 3 상
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int N, K, L;
int board[101][101];

queue<pair<int, char>> q;
deque<pair<int,int>> dq;

bool isValid(int nx, int ny)
{
	// 벽이거나
	if (nx <= 0 || ny <= 0 || nx > N || ny > N) return false;

	// 자신이면
	for (int i = 0; i < dq.size(); i++)
	{
		if (nx == dq[i].first && ny == dq[i].second)
			return false;
	}

	return true;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < K; i++)
	{
		int x, y;
		cin >> x >> y;
		board[x][y] = 1; // apple
	}
	cin >> L;
	for (int i = 0; i < L; i++)
	{
		int x;
		char d;
		cin >> x >> d;
		q.push({ x,d });
	}

	// snake move
	int dir = 0; // 0 우, 1 하, 2 좌, 3 상
	int time = 0;
	int x, nx, y, ny;
	dq.push_back({ 1,1 });
	while(1)
	{
		time++;

		x = dq.front().first;
		y = dq.front().second;

		nx = x + dx[dir];
		ny = y + dy[dir];

		// 유효 검사
		if (isValid(nx, ny) == false) break;

		if (board[nx][ny] == 1)
		{
			board[nx][ny] = 0;
			dq.push_front({ nx,ny });
		}
		else
		{
			dq.push_front({ nx,ny });
			dq.pop_back();
		}

		// 방향 전환의 시간이 왔다면
		if (!q.empty() && time == q.front().first)
		{
			if (q.front().second == 'D')
				dir = (dir + 1) % 4;
			else
				dir = (dir + 3) % 4;

			q.pop();
		}
	}

	cout << time << '\n';
	return 0;
}