[BOJ] 3190 뱀 C++

개요

https://www.acmicpc.net/problem/3190

3190번: 뱀

골드4 난이도 문제다.

풀이

문제를 보고 딱 큐가 떠올랐다.

머리가 늘어나고 꼬리가 사라지는 선입선출 구조!

이동하며 머리가 한 칸 늘어난다.(queue에 push)

이동한 곳에 아무것도 없는 경우 꼬리를 줄이고(queue를 pop) 사과가 있을 경우에는 그대로 진행한다.

만약 뱀 자기 자신이나 벽이 있으면 게임 오버 처리를 해준다.

방향은 1차원 배열을 따로 만들어서 index를 time으로 사용하고 value로 회전 값을 넣어 놓았다.

 

이 문제 게임 만드는 것 같고 참 재밌었다.

강추!!

코드

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
constexpr int LIMIT = 102;
constexpr int dy[] = { 0,1,0,-1 };
constexpr int dx[] = { 1,0,-1,0 };

int N, K, L;
int board[LIMIT][LIMIT];
int turn[LIMIT * LIMIT];
int dir;
queue<pair<int, int>> snakeQ;

int solution()
{
	int time = 0;
	int ny = 1;
	int nx = 1;
	snakeQ.push({ ny,nx });
	while (!snakeQ.empty())
	{
		dir += turn[time];
		if (dir < 0) dir = 3;
		if (dir > 3) dir = 0;

		ny += dy[dir];
		nx += dx[dir];
		time++;

		queue<pair<int, int>> q = snakeQ;
		while (!q.empty())
		{
			if (q.front().first == ny && q.front().second == nx)
				return time;
			q.pop();
		}
		if (ny == 0 || nx == 0 || ny > N || nx > N)
			return time;

		snakeQ.push({ ny, nx });
		if (board[ny][nx]) board[ny][nx] = 0;
		else snakeQ.pop();
	}
	return time;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K;
	int ay;
	int ax;
	for (int i = 0; i < K; i++)
	{
		cin >> ay >> ax;
		board[ay][ax] = 1;
	}
	cin >> L;
	int X;
	char C;
	for (int i = 0; i < L; i++)
	{
		cin >> X >> C;
		if (C == 'L') turn[X] = -1;
		else turn[X] = 1;
	}

	int ans = solution();
	cout << ans;
}