백준 3190_뱀(C++)

 

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

3190번: 뱀

[문제 풀이]

시뮬레이션을 이용하여 문제를 풀었습니다.

 

이 문제는 

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

이 과정을 순서대로 진행해주는 것이 문제의 핵심입니다. 

 

첫 번째 과정은 머리를 다음 칸에 위치시키는 과정입니다. 이 과정에서 벽 이거나 뱀의 몸이면 게임은 종료됩니다. 

 

두 번째 과정은 첫 번째 과정이 무사히 완료되었을 때 뱀이 사과를 먹었는지 안 먹었는지의 여부를 판단해 주고 먹었으면 꼬리를 그대로 두는 경우입니다.

세 번째 과정은 사과가 없는 경우 꼬리를 잘라야 합니다.

이를 위해서 QUEUE를 이용하여 구현하였습니다. 

이번 문제는 X 초 후의 시간의 시점을 정확히 파악하고 문제의 흐름에 맞게 구현해주는 것이 핵심인 것 같습니다.

[코드]

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int N, K, L;
int x = 1, y = 1;
int direct = 0, result = 1;
queue<pair<int, int>> que;
vector<pair<int, char>> v;

int map[101][101] = { 0, };

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

void init();
int moveSnake();

int main() {

	init();
	printf("%d", moveSnake());

	return 0;

}

void init() {

	scanf("%d", &N);
	scanf("%d", &K);

	map[1][1] = 1;
	que.push(make_pair(1, 1));

	for (int i = 0; i < K; i++) {

		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = -1;
	}

	scanf("%d", &L);

	for (int i = 0; i < L; i++) {
		int move;
		char dir;

		scanf("%d %c", &move, &dir);

		v.push_back(make_pair(move, dir));
	}

	v.push_back(make_pair(987654321, 'D'));

}

int moveSnake() {

	bool check = false;

	for (int test = 0; test <= L; test++) {

		int move = v[test].first;
		char dir = v[test].second;

		while (result <= move) {

			x += dx[direct];
			y += dy[direct];

			if (x < 1 || y < 1 || x > N || y > N) {
				check = true;
				break;
			}

			if (map[x][y] != 0 && map[x][y] != -1) {
				check = true;
				break;
			}


			if (map[x][y] == 0) {
				result++;
				map[x][y] = result;
				que.push(make_pair(x, y));
				
				int temp_x = que.front().first;
				int temp_y = que.front().second;
				map[temp_x][temp_y] = 0;
				que.pop();
			}
			else {
				result++;
				map[x][y] = result;
				que.push(make_pair(x, y));
			}	
		}

		if (check)
			break;

		if (dir == 'D') {

			if (direct == 3)
				direct = 0;
			else
				direct++;
		}
		else{
			if (direct == 0)
				direct = 3;
			else
				direct--;
		}

	}


	return result;

}