[삼성 SW 역량 테스트 기출] 뱀

3190번: 뱀

- Dummy라는 도스 게임이라고 한다. 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀이 늘어난다. 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

- 맵은 N*N (2 <= N <= 100), 사과는 k개 (0 <= k <= 100) 있다. 보드의 상하좌우 끝에는 벽이 있고, 맨위 좌측에서 시작하며 좌표는 (1,1), 길이는 1부터 시작한다. 처음엔 오른쪽을 향한다.

 - 생각해줘야 할 조건은 다음과 같다.

 

1. 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다.

2. 만약 이동한 칸에 사과가 있으면, 사과가 없어지고 꼬리는 움직이지 않는다. => 몸길이가 늘어난다.

3. 만약 사과가 없다면, 몸길이를 줄여 꼬리가 위치한 칸을 비운다 => 몸길이가 그대로다.

 

- 사과의 위치, 뱀의 이동 경로가 주어질 때, 게임이 몇 초 안에 끝나는지 구하면 된다.

- 이동경로는 정수 X와 문자 C로 이루어져 있는데, X초가 끝난 뒤에 90도 방향으로 왼쪽(L), 오른쪽(D)으로 회전시키면 된다. 정보는 X가 증가하는 순으로 주어진다.

- 이동 경로를 먼저 생각해보자. 오른쪽으로 가고 있을 때 (y+1) L이 나오면 위로 (x-1), D가 나오면 아래로 (x+1) 간다. 위로 가고 있을 때 (x-1) L이 나오면 왼쪽으로 (y-1), D가 나오면 오른쪽으로 (y+1) 간다. 이를 통해 이동 방향을 추론하면,

 

dx[] = {1,0,-1,0}

dy[] = {0,1,0,-1} 일 때,

L: 오른쪽으로 한칸, D: 왼쪽으로 한칸 (인덱스가 -1이면 3, 4이면 0으로.. 회전목마처럼..)

 

- 이렇게 이동 경로를 생각해주고 구현을 하려고 했는데 생각보다 많이 헤맸다.. 답답해서 어떤 구조를 이용하는 건지 살짝 봤는데 deque였다. 보자마자 무릎을 탁 치고 차근차근 구현을 해나갔다.

- 다음 칸으로 이동 후 사과가 있으면 앞쪽에 push, 없으면 앞쪽에 push 후 뒤쪽을 pop 해주면 전자는 몸이 늘어나고, 후자는 몸길이가 유지된 채 이동한다.

- 벽에 닿는 상황은 쉽게 구현할 수 있지만 까다로웠던 것은 자기에게 닿을 때를 판별하는 것이었다. 문제에서 머리가 다음칸에 위치하는 게 우선이라고 했기 때문에 가장 앞쪽의 위치와 나머지 deque의 위치 중 하나가 중복된다면 자기 몸에 닿아 게임이 끝나게 된다.

- 가장 앞쪽의 위치를 미리 저장해두고, 뒤로 보낸 뒤에, 앞쪽부터 차례로 저장해둔 위치와 비교하는 식으로 deque를 순회하고 중복된 위치가 존재한다면 while문을 벗어나 현재 시간을 답으로 출력하고, 없다면 다음 스텝을 밟아주면 된다.

- 주의해야 할 것은 사과가 없을 경우, 검사가 끝난 뒤에 뒤쪽을 pop 해야한다는 거다. 검사를 하기 전에 pop을 해버리면 머리 쪽이 먼저 늘어난다는 조건에 위배된다. 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

bool map[101][101];
vector<pair<int, char>> dir;
int n, k, l;

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int main() {
	cin >> n >> k;
	int x, y;
	for (int i = 0; i < k; i++) {
		cin >> x >> y;
		map[x][y] = true;
	}
	cin >> l;
	int s; char d;
	for (int i = 0; i < l; i++) {
		cin >> s >> d;
		dir.push_back({ s,d });
	}

	int dsize = dir.size(); // 방향 전환 정보 개수
	deque<pair<int, int>> dq;
	dq.push_back({ 1,1 });
	int nd = 0; // 이동 방향
	int sec = 0; // 초
	int dindex = 0; // 방향 전환 정보 인덱스
	while (!dq.empty()) {
		sec += 1;
		int nx, ny;
		tie(nx, ny) = dq.front();
		nx += dx[nd]; ny += dy[nd]; // 지정된 방향으로 이동
		if (nx <= 0 || nx > n || ny <= 0 || ny > n) break; // 벽에 닿았을 때
		dq.push_front({ nx,ny }); // 앞쪽에 push
		int qsize = dq.size();
		int cx = dq.front().first;
		int cy = dq.front().second;
		auto p = dq.front();
		dq.pop_front();
		dq.push_back(p); // 앞쪽 위치 정보 저장하고 뒤로 보내기
		bool dcheck = false; // 몸에 닿았는지 판별
		for (int i = 1; i < qsize; i++) {
			if (cx == dq.front().first && cy == dq.front().second) {
				dcheck = true;
				break;
			}
			auto p = dq.front();
			dq.pop_front();
			dq.push_back(p);
		}

		if (dcheck) break; // 몸에 닿았을 때
        
		if (map[nx][ny]) map[nx][ny] = false; // 사과 있었다면 없애줌
		else dq.pop_back(); // 없었다면 길이 유지하기 위해 뒤쪽을 pop

		if (dindex < dsize && dir[dindex].first == sec) { // X초가 끝난 뒤에 방향 전환
			if (dir[dindex].second == 'L') {
				nd -= 1;
				if (nd == -1) nd = 3;
			}
			else {
				nd += 1;
				if (nd == 4) nd = 0;
			}
			dindex += 1;
		}
	}

	cout << sec << '\n';
	return 0;
}