acmicpc3190.md

뱀

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

개요

뱀은 처음에 오른쪽을 향해 이동한다. 이동은 1초에 1칸씩이다. 이동한 칸에 사과가 있다면 꼬리는 움직이지 않는다. 이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비워준다. 뱀이 벽이나 자기자신에 부딪히면 게임은 종료된다.

분석

뱀의 이동 이동하며 map을 갱신시켜주면 된다. 하지만 꼬리가 위치한 칸을 비워줄 때 다음 꼬리가 4방향중 어디인지 알 수 없다. 답은 과거에 뱀이 어디로 이동했는지를 알면 된다. 방향의 변화는 시간별로 주어지므로 꼬리가 움직였을 때의 시간과 방향의 변화를 비교하여 과거에 뱀이 어디로 이동했는 지를 알 수 있다.

하지만 공간복잡도가 충분하므로 뱀의 이동시 마다 방향값을 map.dir에 저장한다면 수월하게 꼬리 좌표를 이동시킬 수 있다.

알고리즘

1. 머리 좌표와 꼬리 좌표를 1,1로 초기화한다.
2. 머리 좌표의 방향을 map[x][y][1](map.dir)에 저장한다.
3. 사과가 있다면 먹고 없으면 꼬리좌표를 이동시킨다.
4. 방향을 전환해야 하면 전환한다.

소스

#include <stdio.h>

int map[110][110][2], dd[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

int main()
{
	int tr, tc, nr, nc, od=0,d=0, k, l, n, i, bang[110][2], bi, t=0, ta;
	char a;
	scanf("%d%d", &n, &k);
	for (i = 1; i <= k; i++)
	{
		scanf("%d%d", &tr, &tc);
		map[tr][tc][0] = 2;
	}
	scanf("%d", &l);
	for (i = 1; i <= l; i++)
	{
		scanf("%d %c", &bang[i][0], &a);
		bang[i][1] = (int)a;
	}
	for (i = 0; i <= n+1; i++)
	{
		map[0][i][0] = 1;
		map[n+1][i][0] = 1;
		map[i][0][0] = 1;
		map[i][n+1][0] = 1;
	}
	tr = 1;
	tc = 1;
	nr = 1;
	nc = 1;
	bi = 1;

	while (1)
	{
		t++;
		map[nr][nc][1] = d;
		nr += dd[d][0];
		nc += dd[d][1];
		if (map[nr][nc][0] == 1) break;
		
		if (map[nr][nc][0] == 2) map[nr][nc][0]= 1;
		else
		{
			map[nr][nc][0]=1;
			map[tr][tc][0] = 0;

			ta = map[tr][tc][1];
			tr = tr + dd[ta][0];
			tc = tc + dd[ta][1];

		}

		if (bi <= l && bang[bi][0] == t)
		{
			if (bang[bi][1] == 'L')
			{
				if (d > 0) d = (d - 1) % 4;
				else d = 3;
			}
			else d = (d + 1) % 4;
			bi++;
		}
	}
	printf("%d", t);
}