백준 - 3190번 : 뱀 (C++)

풀이 방법 : 큐, 구현

문제에서 뱀이 입력으로 주어진대로 움직였을 때 자기 자신과 부딪히거나 보드 밖으로 나갈 때가 몇 초인지 구하는 문제이다.

이동 도중 사과를 만나면 자신의 몸의 길이를 1 늘리고 꼬리는 움직이지 않는다. 꼬리 부분이 자라난다고 생각하면 될 것이다.
반대로 사과를 만나지 않은 경우는 이동후 꼬리위치를 비어있는 공간으로 만들어주면 된다.

이를 구현하기 위해 큐를 이용해주었다.처음에 뱀의 위치 즉 머리 좌표를 큐에다 넣어놓고, 이동할 때마다 이동한 좌표들을 큐에다가 넣어주자.

이후 사과를 만나지 않는 경우에는 큐에서 pop처리를 해줘서 가장 먼저 저장된 위치 정보 즉, 꼬리를 삭제 해주면서 그 공간을 비워주면 된다.

반대로 사과를 만난다면 pop처리 하지 않고 다음 턴으로 넘기면 된다.

루프를 도는 도중 종료 조건이 된다면 break 처리해주고 그때까지 걸린 시간을 출력하면 된다.

본 풀이에서는 편의상 비어있는 자리를 0, 뱀의 몸이 위치한 장소를 1, 사과가 위치한 자리를 2 로 표시해주었다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int Board[100][100] = {};
int DirY[4] = { 0, 1, 0, -1 };
int DirX[4] = { 1, 0, -1, 0 };

int CurrentDirIdx = 0;

struct RotInfo
{
	int Sec;
	char Rot;
};

struct SnakeInfo
{
	pair<int, int> Head;
	queue<pair<int, int>> Body;
};

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

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < K; ++i)
	{
		int Raw, Col;
		cin >> Raw >> Col;

		//사과의 위치는 2로 저장
		Board[Raw - 1][Col - 1] = 2;
	}

	int L;
	cin >> L;

	int CurrentSeconds = 1;

	vector<RotInfo> vecRotInfo(L);
	int CurrentRotIdx = 0;

	for (int i = 0; i < L; ++i)
	{
		cin >> vecRotInfo[i].Sec >> vecRotInfo[i].Rot;
	}

	//뱀의 몸이 위치한 곳은 1로 저장
	Board[0][0] = 1;
	SnakeInfo Snake;
	Snake.Head = pair<int, int>(0, 0);

	while (true)
	{
		int NextHeadY = Snake.Head.first + DirY[CurrentDirIdx];
		int NextHeadX = Snake.Head.second + DirX[CurrentDirIdx];

		bool bIsOutOfBound = NextHeadY >= N || NextHeadY < 0 || NextHeadX >= N || NextHeadX < 0;

		if (bIsOutOfBound)
			break;

		bool bIsCollision = (Board[NextHeadY][NextHeadX] == 1);

		if (bIsCollision)
			break;

		Snake.Body.push(Snake.Head);

		Snake.Head.first = NextHeadY;
		Snake.Head.second = NextHeadX;

		bool bIsApple = (Board[NextHeadY][NextHeadX] == 2);

		if (!bIsApple)
		{
			pair<int, int> Tail = Snake.Body.front();
			Snake.Body.pop();
			Board[Tail.first][Tail.second] = 0;
		}

		Board[NextHeadY][NextHeadX] = 1;

		if (CurrentRotIdx < L)
		{
			if (CurrentSeconds == vecRotInfo[CurrentRotIdx].Sec)
			{
				if (vecRotInfo[CurrentRotIdx].Rot == 'L')
				{
					--CurrentDirIdx;
					if (CurrentDirIdx == -1)
						CurrentDirIdx = 3;
				}

				else
				{
					++CurrentDirIdx;

					if (CurrentDirIdx == 4)
						CurrentDirIdx = 0;
				}

				++CurrentRotIdx;
			}
		}

		++CurrentSeconds;
	}

	cout << CurrentSeconds;
}