백준 - 뱀 (3190) [C++]

이 문제는 덱을 이용한 시뮬레이션 문제이다. 덱을 이용하여 뱀을 표현하는 생각을 하는 것이 핵심이다. 처음에는 매 초마다 덱을 순회하여 보드에 표시했다가 초가 끝나면 다시 지우는 방식을 생각했으나, 사과의 유무에 상관없이 덱의 front에 추가 하면 되고, 사과가 없으면 덱의 back 부분을 pop 해주면 굳이 썼다 지웠다 할 필요가 없었다. 어려운 구현 문제는 단계를 나눠서 차근차근 풀어나가야 해결할 수 있는 것 같다.

 

 

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

#define MAX 100

#define RIGHT 1
#define LEFT 2
#define UP 3
#define DOWN 4

int n, k, l;
int board[MAX][MAX];
deque<pair<int, char>> q;

bool inRange(int y, int x)
{
	if (0 <= y && y < n && 0 <= x && x < n)
	{
		return true;
	}
	return false;
}

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

	cin >> n;
	cin >> k;

	for (int i = 0; i < k; i++)
	{
		int r, c;

		cin >> r >> c;
		board[r - 1][c - 1]++;
	}

	cin >> l;
	for (int i = 0; i < l; i++)
	{
		int x;
		char c;

		cin >> x >> c;

		q.push_back(make_pair(x, c));
	}

	int sec = 0;
	int direction = RIGHT;
	deque<pair<int, int>> snake;
	snake.push_back(make_pair(0, 0));
	board[0][0] = -1;
	while (true)
	{
		sec++;
		pair<int, int> head = snake.front();

		// 몸길이 늘리기
		int nextY = head.first, nextX = head.second;
		switch (direction)
		{
		case RIGHT:
			nextX++;
			break;
		case LEFT:
			nextX--;
			break;
		case UP:
			nextY--;
			break;
		case DOWN:
			nextY++;
			break;
		}

		// 만약 자기 몸에 부딪히거나 칸을 벗어나면 종료
		if (!inRange(nextY, nextX))
		{
			break;
		}
		if (board[nextY][nextX] == -1)
		{
			break;
		}

		// 다음 칸 사과 판정
		if (board[nextY][nextX] == 1)
		{
			board[nextY][nextX] = -1;
			snake.push_front(make_pair(nextY, nextX));
		}
		else if (board[nextY][nextX] == 0)
		{
			board[nextY][nextX] = -1;
			snake.push_front(make_pair(nextY, nextX));
			
			pair<int, int> temp = snake.back();
			snake.pop_back();
			board[temp.first][temp.second] = 0;
		}

		// 방향 전환 정보
		if (!q.empty())
		{
			pair<int, char> change = q.front();

			if (change.first == sec)
			{
				q.pop_front();

				if (change.second == 'L')
				{
					switch (direction)
					{
					case RIGHT:
						direction = UP;
						break;
					case LEFT:
						direction = DOWN;
						break;
					case UP:
						direction = LEFT;
						break;
					case DOWN:
						direction = RIGHT;
						break;
					}
				}
				else if (change.second == 'D')
				{
					switch (direction)
					{
					case RIGHT:
						direction = DOWN;
						break;
					case LEFT:
						direction = UP;
						break;
					case UP:
						direction = RIGHT;
						break;
					case DOWN:
						direction = LEFT;
						break;
					}
				}
			}
		}
	}

	cout << sec << '\n';

	return 0;
}