[백준][3190번] 뱀

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

3190번: 뱀

풀이과정

1. 특별한 알고리즘없이 문제의 흐름대로 풀면 풀리는 문제였다.

 

2. 뱀의 길이가 계속 늘어 날 수 있어 vector를 이용하여 뱀의 위치 정보를 가졌다.

 

3. 뱀의 현재 위치를 담은 visited배열을 이용하여 "자신의 몸의 닿을 경우 게임은 종료된다." 를 체크했다.

 

결과

 

소스코드

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
int map[101][101];
int visited[101][101];
struct info {
	int t;
	char dir;
}typedef info;
struct dummy {
	int x;
	int y;
	int d;
}typedef dummy;
int dx[4] = { 1, 0 ,-1 ,0 };
int dy[4] = { 0, 1, 0, -1 };
vector<info> g_info;
vector<dummy> g_dummy;
int N, L, K;
void changeDirection(char dir)
{
	if (dir == 'L') //left 90'
	{
		g_dummy[0].d--;
		if (g_dummy[0].d < 0) {
			g_dummy[0].d = 3;
		}
	}
	else {
		g_dummy[0].d++;
		if (g_dummy[0].d > 3) {
			g_dummy[0].d = 0;
		}
	}
}
int solution()
{
	int answer = 0;
	visited[0][0] = 1;
	info change = g_info[0]; g_info.erase(g_info.begin());
	while (!g_dummy.empty()) {
		//자기 몸 또는 벽
		answer++;
		int nx = g_dummy[0].x + dx[g_dummy[0].d];
		int ny = g_dummy[0].y + dy[g_dummy[0].d];
		
		if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[ny][nx] == 1) {
			return answer;
		}
		else {
			visited[ny][nx] = 1;
			if (map[ny][nx] == 1) {
				map[ny][nx] = 0;
				dummy next = { nx, ny, g_dummy[0].d };
				g_dummy.insert(g_dummy.begin(), next);
			}
			else {
				dummy next = { nx, ny, g_dummy[0].d };
				g_dummy.insert(g_dummy.begin(), next);
				dummy last = g_dummy.back();
				visited[last.y][last.x] = 0;
				g_dummy.pop_back();
			}
		}

		if (change.t == answer) {
			changeDirection(change.dir);
			if (g_info.size() > 0) {
				change = g_info[0]; g_info.erase(g_info.begin());
			}
		}
	}
}
int main()
{
	scanf("%d", &N);
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		int x, y;
		scanf("%d %d", &y, &x);
		map[y-1][x-1] = 1;
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		int t;
		char ch;
		scanf("%d %c", &t, &ch);
		info tmp = { t, ch };
		g_info.push_back(tmp);
	}
	dummy tmp = { 0, 0, 0 };
	g_dummy.push_back(tmp);
	printf("%d\n", solution());
}