[BOJ][3190] 뱀

문제

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

3190번: 뱀

풀이

문제에서 고려해야할 가장 중요한 점은 ① x초 후 c로 방향이 변환 되는것 ② 사과를 먹을 경우 길이가 증가 ③ 공간 이탈 혹은 본인 몸 부딪힐 경우 break, 이 세가지 입니다.

문제에서는 좌표 값을 (1,1) 시작으로 설정했지만 저는 각각 -1씩 하여 문제를 풀었습니다. 움직이는 방향은 dx, dy를 설정하여 시계방향으로 값을 셋팅하고, 방향이 바뀔때마다 dir변수를 두어 +1 혹은 -1 을 통해 방향을 변환하였습니다.

사과가 있을 경우, len_dir이라는 큐를 두어 뱀이 위치한 방향 좌표를 넣었습니다. 사과가 없는 경우, 뱀의 새로운 좌표를 넣어주고 큐에 담겨있던 뱀의 꼬리 좌표를 0으로 만든뒤 큐에서 pop하였습니다. 

코드 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, k;
int map[101][101];
queue<pair<int, char>>  time_table;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
void main() {
	/*
	1. default : 오른쪽
	2. 몸길이 늘려 머리를 다음 칸에 위치
	3. 이동 칸에 몸길이를 줄여 꼬리 위치칸 비우기
	
	res = 게임이 몇초에 끝나나

	*/
	cin >> n;
	cin >> k;
	//사과의 위치
	int p, q, l;
	memset(map, 0, sizeof(map));
	for (int i = 0; i < k; i++) {
		cin >> p >> q;
		map[p - 1][q - 1] = 1;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		int x;
		char c;
		cin >> x >> c;
		// x초 후 c로 dir변환 ; 왼 : L , 오 : D, 90도
		time_table.push(make_pair(x+1, c));
	}
	bool boom = false;
	
	//시간
	int t = 0;
	//dir순번
	int dir = 0; //순서 : 동 남 서 북 (시계방향)
	int len = 1;

	//벽충돌 & 본인과 부딪히면 종료
	//뱀의 시작점과 끝점을 담는 변수
	int a = 0;
	int b = 0;
	int end_a = 0;
	int end_b = 0;
	map[a][b] = -1;

	//뱀이 차지하는 위치 담는 공간
	queue<pair<int,int>> len_dir;
	len_dir.push(make_pair(0, 0));

	//부딪힐때까지 계속 진행
	while (!boom) {
		t++;

		int c_dir = -1;
		//방향변환여부
		if (!time_table.empty()) {
			c_dir = time_table.front().first;
		}
		else
			c_dir = -1;

		//특정 시의 방향 변환
		if (c_dir == t) {
			char dir_char = time_table.front().second;
			if (dir_char == 'L') {
				if (dir == 0) {
					dir = 3;
				}
				else
					dir -= 1;
			}
			else {
				if (dir == 3) {
					dir = 0;
				}
				else 
					dir += 1;
			}
			time_table.pop();
		}

		//뱀 머리 이동
		int na = a + dx[dir];
		int nb = b + dy[dir];
		//범위 이탈시
		if (na < 0 || nb < 0 || na >= n || nb >= n) {
			a = na;
			b = nb;
			boom = true;

			break;
		}
		//본인 부딪힐 경우
		if (map[na][nb] == -1) {
			a = na;
			b = nb;
			boom = true;
			
			break;
		}

		//사과가 있을 경우
		if (map[na][nb] == 1) {
			len_dir.push(make_pair(na, nb));
			map[na][nb] = -1;
		}
		//사과가 없을 경우
		else {
			len_dir.push(make_pair(na, nb));
			map[na][nb] = -1;
			map[end_a][end_b] = 0;
			len_dir.pop();
			end_a = len_dir.front().first;
			end_b = len_dir.front().second;
		}
		//뱀머리 갱신
		a = na;
		b = nb;
	}
	cout << t;
}