[백준 3190] 뱀(C++)

문제의 링크 : https://www.acmicpc.net/problem/3190

3190번: 뱀

문제 풀이

문제 유형 : Simulation

뱀이 늘어나고 줄어드는 것을 deque 자료구조를 이용해서 구현했습니다.

뱀이 꼬리가 줄어들면 deque의 앞에서 삭제하고, 뱀의 머리가 늘어나면 deque의 뒤에 추가하는 방법입니다.

 

천천히 시뮬레이션을 생각해봅시다.

 

뱀이 (1, 1) 동쪽에서 시작합니다.

뱀이 한 칸을 먼저 전진한다고 가정하고 사과가 있는지 없는지 판단합니다.

i) 거기에 사과가 있다면? 뱀의 꼬리는 줄어들지 않게 되고, 뱀의 머리에 한 칸 전진 한 좌표를 넣어줍니다.

즉, 뱀의 길이가 늘어나게 됩니다.

따라서 deque에는 tail - (1, 1) , (1, 2) - head 입니다.

ii) 거기에 사과가 없었다면? 뱀의 꼬리는 줄어들게 되고, 뱀의 머리에 한 칸 전진 한 좌표를 넣어줍니다.

뱀의 길이가 줄어들게 됩니다.

따라서 deque에는 tail - (1, 2) - head입니다.

 

뱀이 이동을 마쳤다면, 뱀의 방향 변환 정보를 확인합니다.

동 = 0, 서 = 1, 남 = 3, 북 = 4라고 가정하고 보면

현재의 time과 뱀의 방향에서의 time이 일치한다면 그 방향으로 뱀의 방향인 dir를 바꿔줍니다.

 

예를 들어서 현재 dir 가 동쪽을 가리킨다고 한다면, (dir == 0)

여기에서 현재의 time과 뱀의 방향에서의 time이 일치할 때,

뱀의 방향 변환 정보가 'D' 라면, 동쪽에서 오른쪽으로 꺾게 되면 남쪽입니다. 따라서 (dir == 3)으로 변환해주는 함수를 작성하면 됩니다.

 

소스 코드

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

int N, K, L, X, ans;
int stage[101][101];

deque<pair<int, char>> dq;

// 동, 서, 남, 북
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int ChangeDirection(int d, char ch)
{
	if (d == 0)
	{
		if (ch == 'L') return 3;
		else return 2;
	}
	else if (d == 1)
	{
		if (ch == 'L') return 2;
		else return 3;
	}
	else if (d == 2)
	{
		if (ch == 'L') return 0;
		else return 1;
	}
	else if (d == 3)
	{
		if (ch == 'L') return 1;
		else return 0;
	}
}

int Simulation()
{
	int x = 1, y = 1, time = 0, dir = 0;
	deque<pair<int, int>> snake_pos; // 뱀을 표현

	// 뱀의 시작
	stage[x][y] = 1; 
	snake_pos.push_back({ x,y });

	while (1)
	{
		time++;

		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx < 1 || nx > N)   return time;
		if (ny < 1 || ny > N)   return time;
		if (stage[nx][ny] == 1) return time;

		if (stage[nx][ny] == -1)
		{
			stage[nx][ny] = 1;
			snake_pos.push_back({ nx,ny });
		}
		
		else
		{
			stage[nx][ny] = 1;
			snake_pos.push_back({ nx,ny });
			// 사과가 없다면, 뱀의 머리는 뱀의 꼬리를 줄여야한다. -> 잘라야한다.
			int p1 = snake_pos.front().first;
			int p2 = snake_pos.front().second;
			snake_pos.pop_front();
			stage[p1][p2] = 0;
		}

		if(!dq.empty() && dq.front().first == time)
		{
			dir = ChangeDirection(dir, dq.front().second);
			dq.pop_front();
		}

		x = nx;
		y = ny;
	}
}

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

	//freopen("input.txt", "r", stdin);
	cin >> N >> K;
	for (int i = 0; i < K; i++)
	{
		int r, c;
		cin >> r >> c;
		stage[r][c] = -1;
	}

	cin >> L;
	dq.resize(L);
	for (int i = 0; i < L; i++)
	{
		int num;
		char ch;
		cin >> num >> ch;
		dq[i] = { num, ch };
	}

	int ans = Simulation();
	cout << ans;
	return 0;
}