[C/C++] 백준 - 3190번 (뱀) 시물레이션

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

3190번: 뱀

 

삼성 기출 문제인데 내가 이걸 풀었다니 3월부터 알고리즘 시작해서 가장 기쁜 순간이다.

시물레이션 문제라 엄청 높은 난이도의 문제는 아니지만 그래도 풀었다는 것에 의의를 두고 더 열심히 해야겠다.

 

뱀의 길이를 생각하는 것은 덱을 사용해서 다음 위치에는 front에 좌표를 넣어주고

사과를 못먹었을 시에 꼬리를 잘라주어야 하기 때문에 back을 잘라주는 식으로 구현했다.

방향을 바꾸는 것은 큐에 정보를 넣어 확인하는 식으로 다음 방향을 정해주었다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#define sz 100+1

using namespace std;

// 사과를 먹으면 뱀 길이가 늘어난다
// 벽 또는 자기자신의 몸과 부딪히면 게임 끝

int map[sz][sz];
int N, K, L;
int change_time;
int cur_x=1, cur_y=1;
char Dir; int direct = 1; 

queue<pair<int, char>> q;
deque<pair<int, int>> v;

void input_Data() {
	cin >> N;
	cin >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		map[x][y] = 54321;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> change_time >> Dir;
		q.push({ change_time, Dir });
	}
	v.push_front({ 1,1 });
	map[1][1] = 1;
}

int possible(int dir) {
	int nextX, nextY;
	switch (dir) {
	case 0:
		nextX = cur_x - 1;
		nextY = cur_y;
		break;
	case 1:
		nextX = cur_x;
		nextY = cur_y + 1;
		break;
	case 2:
		nextX = cur_x + 1;
		nextY = cur_y;
		break;
	case 3:
		nextX = cur_x;
		nextY = cur_y - 1;
		break;
	}
	
	if (map[nextX][nextY] == 1) 
		return 0;
	else {
		cur_x = nextX;
		cur_y = nextY;
		return 1;
	}
}

void Move_snake() {
	if (map[cur_x][cur_y] == 54321) {
		v.push_front({ cur_x,cur_y });
		map[cur_x][cur_y] = 1;
	}
	else {
		map[cur_x][cur_y] = 1;
		v.push_front({ cur_x,cur_y });
		
		int a = v.back().first;
		int b = v.back().second;
		map[a][b] = 0;
		v.pop_back();
	}
}

void Print() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}

void change_Dir_left(int dir) {
	switch (direct) {
	case 0:
		direct = 3;
		break;
	case 1:
		direct = 0;
		break;
	case 2:
		direct = 1;
		break;
	case 3:
		direct = 2;
		break;
	}
}

void change_Dir_right(int dir) {
	switch (direct) {
	case 0:
		direct = 1;
		break;
	case 1:
		direct = 2;
		break;
	case 2:
		direct = 3;
		break;
	case 3:
		direct = 0;
		break;
	}
}

int main() {
	input_Data();
	
	direct = 1;
	int time = 1;
	while (1) {
		//Print();
		if (!possible(direct)) break;
		if (cur_x < 1 || cur_x > N || cur_y < 1 || cur_y > N) break;
		
		if (!q.empty()) {
			int switch_time = q.front().first;
			char switch_dir = q.front().second;
			Move_snake();
			if (time == switch_time) {
				if (switch_dir == 'L') {
					change_Dir_left(direct);
				}
				else {
					change_Dir_right(direct);
				}
				q.pop();
			}
		}
		else {
			Move_snake();
		}

		time++;
	}
	cout << time << "\n";

	return 0;
}