[C++][BOJ] 삼성 SW 역량 테스트 기출 문제 - 3190번 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

이번 문제는 큐를 활용하여 가는 곳의 위치를 저장하고 사과가 없으면 큐의 맨 앞을 제거하고 뱀의 머리 좌표를 큐에 넣고, 사과가 있으면 그냥 뱀의 머리 좌표만 큐에 넣어가면서 큐를 업데이트해주는 문제였다.

 

이 것을 구현하기 위해 map을 -1로 초기화해주고 사과가 있는 위치를 APPLE이라고 표시를 해주고 방향이 바뀌는 시간과 방향을 배열에 저장해 준다.

 

무조건 처음에는 오른쪽이므로 오른쪽을 기준으로 char가 오면 L이면 90도로 왼쪽으로 회전된 방향을 저장하고 D가 오면 90도로 오른쪽으로 회전된 방향을 저장한다. getDirection이라는 함수를 구현해 그 방향을 구해서 저장한다.

 

처음에 뱀의 머리(head)는 (1, 1) 에서 부터 시작하므로 큐에 (1, 1)을 집어넣고 map도 head로 변경한다. 

 

항상 queue의 뒤쪽을 가져온다. 왜나하면 queue의 뒤쪽이 뱀의 머리이기 때문이다. queue의 앞쪽은 뱀의 꼬리라고 생각하면 된다.

 

그다음 그 좌표에 방향으로 뱀의 머리를 이동시키고, 그 이동시킨 좌표가 우리의 map의 범위를 벗어나면 while문을 종료한다.

 

벗어나지 않았으면 map에 사과가 있는지 없는지를 판단하여 해당 조건에 따라 큐와 map을 업데이트해준다.

 

여기서 주의해야 될 부분은, map에 사과가 없고 빈 곳이면 꼬리를 큐에서 제거하고 그 꼬리 부분은 이제 map에서 빈 곳이 되기 때문에 다시 -1로 초기화를 해줘야 한다. map에 만약 몸통이 있는 곳이면 그대로 map을 빠져나온다.

 

해당 time마다 뱀의 방향 정보와 일치하는지 확인하고 일치하면 방향을 변경해주면 된다.

 

break를 통해 while문을 빠져나왔으면 그때의 timer을 return 하면 정답이 된다.

 

그럼 이제 정답 코드를 살펴보자.

#include <iostream>
#include <queue>
using namespace std;
#define MAX_MAP 102
#define APPLE 3
#define BODY 2
#define TAIL 1
#define HEAD 0

int map[MAX_MAP][MAX_MAP];
int N, K, L;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
struct Rotate
{
	int time;
	int dir;
};
Rotate r[MAX_MAP];
int getDirection(int cur, char dir)
{
	//왼쪽
	if (cur == 0)
	{
		if (dir == 'L')
		{
			//아래
			return 3;
		}
		else
		{
			//위
			return 2;
		}
	}
	//위
	else if (cur == 2)
	{
		if (dir == 'L')
		{
			//왼쪽
			return 0;
		}
		else
		{
			//오른쪽
			return 1;
		}
	}
	//오른쪽
	else if (cur == 1)
	{
		if (dir == 'L')
		{
			//위
			return 2;
		}
		else
		{
			//아래
			return 3;
		}
	}
	//아래
	else
	{
		if (dir == 'L')
		{
			//오른쪽
			return 1;
		}
		else
		{
			//왼쪽
			return 0;
		}
	}
	return -1;
}
int solve()
{
	queue<pair<int, int>> q;
	pair<int, int> head;
	head.first = 1, head.second = 1;
	q.push(head);
	map[head.first][head.second] = HEAD;
	int direction = 1;
	int timer = 0;
	int r_counter = 0;
	while (1)
	{
		timer++;
		head = q.back();

		int n_x = head.second + dx[direction];
		int n_y = head.first + dy[direction];
		//cout << "n_y = " << n_y << " n_x = " << n_x << " timer = " << timer << endl;
		if (n_y > N || n_x > N || n_y < 1 || n_x < 1) break;

		if (map[n_y][n_x] == APPLE)
		{
			//head의 위치를 이동, 꼬리는 변화없음
			head.second = n_x;
			head.first = n_y;
			//map의 사과를 head로 변경
			map[n_y][n_x] = HEAD;
			q.push(head);
		}
		else if (map[n_y][n_x] == -1)
		{
			pair<int, int> tail;
			tail = q.front();
			q.pop();
			head.second = n_x;
			head.first = n_y;
			map[n_y][n_x] = HEAD;
			q.push(head);
			map[tail.first][tail.second] = -1;
		}
		//body나 머리, 꼬리, 벽이라면
		else
		{
			break;
		}
		if (timer == r[r_counter].time)
		{
			direction = r[r_counter].dir;
			r_counter++;
		}
	}
	return timer;
}
int main()
{
	cin >> N;
	cin >> K;
	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j <= N; j++)
		{
			map[i][j] = -1;
		}
	}
	for (int i = 0; i < K; i++)
	{
		int x, y;
		cin >> y >> x;
		map[y][x] = APPLE;
	}
	cin >> L;
	int cur = 1;
	for (int i = 0; i < L; i++)
	{
		int _time;
		char _dir;
		cin >> _time >> _dir;
		cur = getDirection(cur, _dir);
		r[i].dir = cur;
		r[i].time = _time;
	}
	cout << solve() << endl;
}