[백준/BOJ] 백준 3190번 : 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

int snake[101][101];를 이용해 현재 뱀이 속해있는 위치들을 표시하였다. 그리고 deque를 이용해 deque의 front를 뱀의 머리(head)로 나타내고, back을 꼬리(tail)로 나타냈다.

 

코드

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

int n, k;
int l;
int board[101][101];
int snake[101][101];
char turn[10001];

void Pre()
{
	for (int i = 0; i < 101; i++)
	{
		turn[i] = '.';
		for (int j = 0; j < 101; j++)
		{
			board[i][j] = 0;
			snake[i][j] = 0;
		}
	}
}

int Solve(pair<pair<int, int>, int> start)
{
	int cnt = 0;

	//snake가 속해있는 위치들을 표시
	snake[start.first.first][start.first.second] = 1;

	//snake가 속해있는 위치들을 저장
	deque <pair<pair<int, int>, int>> dq;

	dq.push_back(start);

	while (1)
	{
		pair<pair<int, int>, int> head = dq.front();
		pair<pair<int, int>, int> tail = dq.back();

		cnt++;

		pair<pair<int, int>, int> n_head; //다음에 이동할 head 정보 저장 
		n_head = head;

		//현재 head가 왼쪽을 향하고 있을때
		if (head.second == 0)
		{
			n_head.first.second--;

			if (turn[cnt] == 'L')
			{
				n_head.second = 3;
			}

			else if (turn[cnt] == 'D')
			{
				n_head.second = 1;
			}
		}

		//현재 head가 위쪽을 향하고 있을때
		else if (head.second == 1)
		{
			n_head.first.first--;

			if (turn[cnt] == 'L')
			{
				n_head.second = 0;
			}

			else if (turn[cnt] == 'D')
			{
				n_head.second = 2;
			}
		}
		
		//현재 head가 오른쪽을 향하고 있을때
		else if (head.second == 2)
		{
			n_head.first.second++;

			if (turn[cnt] == 'L')
			{
				n_head.second = 1;
			}

			else if (turn[cnt] == 'D')
			{
				n_head.second = 3;
			}
		}

		//현재 head가 아래쪽을 향하고 있을때
		else if (head.second == 3)
		{
			n_head.first.first++;

			if (turn[cnt] == 'L')
			{
				n_head.second = 2;
			}

			else if (turn[cnt] == 'D')
			{
				n_head.second = 0;
			}
		}

		//뱀이 벽 또는 자기자신의 몸과 부딪혔을때
		if (n_head.first.first < 1 || n_head.first.first > n || n_head.first.second < 1 || n_head.first.second > n || snake[n_head.first.first][n_head.first.second] == 1)
			return cnt;

		//다음 위치에 사과가 없을때
		if (board[n_head.first.first][n_head.first.second] != 1)
		{
			//꼬리 위치를 비운다
			snake[tail.first.first][tail.first.second] = 0;
			dq.pop_back();
		}

		//다음 위치가 사과일때
		else if (board[n_head.first.first][n_head.first.second] == 1)
		{
			//해당 위치의 사과는 없어진다
			board[n_head.first.first][n_head.first.second] = 0;
		}

		//이동한 위치의 뱀 정보를 저장
		snake[n_head.first.first][n_head.first.second] = 1;
		dq.push_front(n_head);
	}

	return -1;
}

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

	Pre();

	int a, b;
	int x;
	char c;

	cin >> n;
	
	cin >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> a >> b;
		board[a][b] = 1;
	}

	cin >> l;

	for (int i = 0; i < l; i++)
	{
		cin >> x >> c;
		turn[x] = c; //x초가 끝난뒤 어떤 방향으로 회전하는지 저장
	}

	//시작은 (1,1)에서 오른쪽(2)을 향하고 있다.
	pair<pair<int, int>, int> start = make_pair(make_pair(1, 1), 2);

	cout << Solve(start);

	return 0;
}