(c++)백준 3190번: 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

[풀이]

문제에 적힌 규칙대로 시뮬레이션 해주면 되는 문제다.

-사과의 위치는 Map[N+1][N+1]배열에 1로 표시해 주었고, 뱀이 있는 자리는 bool Snake[N+1][N+1]에 ture로 표시해 주었다.

-꼬리의 소재를 알기 위해 queue<SnakePos>s에 뱀의 위치정보를 넣어주고, 꼬리가 이동하면 pop해주었다.

-몇 초 후에 어떤 방향으로 바뀌는지에 대한 정보는 char Change[10001]에 인덱스를 초로 두고 문자를 넣어 매 초마다 방향이 바뀌는지 확인해주었다.

-재귀함수를 사용하여 구현해주었다.

 

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

struct SnakePos {
	int x, y;
};

int N, K, L;
int Map[101][101];//인덱스 1~N
bool Snake[101][101];//뱀이 있는 자리
queue<SnakePos>s;//뱀 꼬리 소재 알기 위한 벡터
char Change[10001];//몇초 후에 어떤 방향으로 바뀌는지
int time = 0;
const int dxy[][2] = { {-1,0},{0,-1},{1,0},{0,1} };//방향 인덱스 0~3

int changeDir(int curd, char nd) {
	int ndir = curd;
	if (nd == 'L'){
		ndir = ndir + 1;
		if (ndir == 4)ndir = 0;
	}
	else if (nd == 'D') {
		ndir = ndir - 1;
		if (ndir == -1)ndir = 3;
	}
	return ndir;
}

void game(int hx, int hy, int tx, int ty, int dir, int t) {
	time = t;
	int nx = hx + dxy[dir][0];
	int ny = hy + dxy[dir][1];
	
	//뱀이 벽에 부딪히면
	if (nx <= 0 || nx > N || ny <= 0 || ny > N)
		return;
	//자기자신의 몸과 부딪히면
	if (Snake[nx][ny] == true)
		return;

	//머리 다음칸으로
	Snake[nx][ny] = true;
	s.push({ nx,ny });

	//방향 전환 확인
	int ndir = changeDir(dir, Change[t]);
	//사과가 있으면
	if (Map[nx][ny] == 1) {
		//사과 먹기
		Map[nx][ny] = 0;
		//몸 길이 늘어나므로 꼬리는 움직이지 않음
		game(nx, ny, tx, ty, ndir, t + 1);
	}
	//사과가 없을 경우
	else {
		//꼬리 줄어듦
		s.pop();
		Snake[tx][ty] = false;
		int ntx = s.front().x;
		int nty = s.front().y;
		game(nx, ny, ntx, nty, ndir, t + 1);
	}
}

void solution() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		Map[x][y] = 1;//사과가 있는 자리는 1
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		int x;
		char l;
		cin >> x >> l;
		Change[x] = l;
	}
	s.push({ 1,1 });
	//머리와 꼬리 모두 (1,1)에 있고 시작 방향은 오른쪽, 첫번째 움직였을 때 시간은 1
	game(1, 1, 1, 1, 3, 1);
	cout << time << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}