[ 백준 3190 ] 뱀 (C++)

3190번: 뱀

 

 

문제!

---

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

---

일반적인 뱀 게임입니다!

사과를 먹으면 뱀의 길이가 늘어나고 아닐시 계속이동하다가 벽이나 자신의 몸에 부딪히면 끝나는 규칙의 게임입니다.

 

처음에 생각했을때에는 que를 가지고 해결하려 했습니다.

 

사과를 먹을시에는 앞에 몸을 추가해주고, 일반 이동시에는 앞에 몸을 추가해줌과 동시에 뒤쪽을 땡겨 줘야 겠다!

라고 생각했으나 

 

이 방법보다는 deque방식으로 처리하는것이 더 빠르다는것을 깨닫고... 수정!

 

 

그럼 시작하겠습니다.

---

먼저 각종 변수를 저장해줍시다.

int n = 0, k = 0, l = 0;
int map[102][102] = { 0 };

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 }; // 상하 좌우

int now_time = 0;
int now_dir = 3;// 현재방향에서 좌우봐야됨..

deque<pair<int, int>>snake;
pair<int, int>head;

다음은 main에서 입력을 받고

cin >> n;
	cin >> k;


	for (int i = 0; i < n+1; i++) {// 틀 만들기
		map[i][0] = 3;
		map[i][n+1] = 3;
		map[0][i] = 3;
		map[n + 1][i] = 3;
	}

	snake.push_front({ 1, 1 }); // 뱀 시작 오른쪽으로 갈것
	map[1][1] = 3;

	int app_y, app_x;
	for (int i = 0; i < k; i++) {
		cin >> app_y >> app_x;
		map[app_y][app_x] = 1; // 사과

	}
	cin >> l;

저는 틀의 범위를 생각 하지 않기위해 틀을 만들어 주었습니다.

3 3 3 3 3

3 1 1 1 3

3 1 1 1 3

3 1 1 1 3

3 3 3 3 3

 

이런식으로 만들어지게!

그리고 뱀의 몸 또한 3으로 정의 해주고

사과는 1로 지정했습니다.

 

 

 

다음은 현재 위치에 위치해도 되는지에 대한 함수를 하나 만들어 주었습니다.

bool check(int y,int x) {// 가도되는 위치인지
	if (map[y][x] == 3) {
		return false;
	}
	return true;
}

 

그리고 위의 함수를 이용하여 이동하는 함수를 만들어 주었습니다.

int update() {
	now_time += 1;
	int apple = 0;
	head = snake.front();
	
	if (!check(head.first + dy[now_dir], head.second + dx[now_dir])) {// 가능한지
		
		return 1;
	}

	snake.push_front({ head.first + dy[now_dir],head.second + dx[now_dir] });// 머리이동

	if (map[head.first + dy[now_dir]][head.second + dx[now_dir]]!=1) {// 1사과가 아닐때
		map[snake.back().first][snake.back().second] = 0;
		snake.pop_back();
	}

	map[head.first + dy[now_dir]][head.second + dx[now_dir]] = 3;
	
	return 0;
}

 

이동한 칸이 막혀있을시에는 1을 출력하여 바로 현재시간을 출력하도록 했고

사과일때는 앞쪽으로만 하나를 추가

빈칸일때는 앞쪽에서는 하나를 추가 , 그리고 맨뒤쪽에서는 pop처리 해주었습니다.

 

 

그리고 밑은 main안에서 입력에 따라 실제 방향과 값을 출력해주는 부분을 구현했습니다.

	string dir_L;

	int move_time = 0;
	for (int i = 0; i < l; i++) {
		cin >> move_time >> dir_L;
		

		while (move_time!= now_time) {// 시간이 아직 안됨
			
			if (update()) {
				cout << now_time;
				return 0;
			}
			

		}
	
		if (dir_L == "D") {// 오른
			if (now_dir == 0) {
				now_dir = 3;
			}
			else if (now_dir == 1) {
				now_dir = 2;
			}
			else if (now_dir == 2) {
				now_dir = 0;
			}
			else {
				now_dir = 1;
			}

		}
		else {
			if (now_dir == 0) {
				now_dir = 2;
			}
			else if (now_dir == 1) {
				now_dir = 3;
			}
			else if (now_dir == 2) {
				now_dir = 1;
			}
			else {
				now_dir = 0;
			}
		}
		//---------------방향결정

		if (update()) {
			cout << now_time;
			return 0;
		}
		
	}


	while (1) {

		if (update()) {
			cout << now_time;
			return 0;
		}
	}

 

 

좀 길긴 했지만 구현 성공 했네요;

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;


int n = 0, k = 0, l = 0;
int map[102][102] = { 0 };

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 }; // 상하 좌우

int now_time = 0;
int now_dir = 3;// 현재방향에서 좌우봐야됨.. 

deque<pair<int, int>>snake;
pair<int, int>head;

void prin() {// 프린트
	for (int i = 0; i < n + 2; i++) {
		for (int j = 0; j < n + 2; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

bool check(int y,int x) {// 가도되는 위치인지
	if (map[y][x] == 3) {
		return false;
	}
	return true;
}

int update() {
	now_time += 1;
	int apple = 0;
	head = snake.front();
	
	if (!check(head.first + dy[now_dir], head.second + dx[now_dir])) {// 가능한지
		
		return 1;
	}

	snake.push_front({ head.first + dy[now_dir],head.second + dx[now_dir] });// 머리이동

	if (map[head.first + dy[now_dir]][head.second + dx[now_dir]]!=1) {// 1사과가 아닐때
		map[snake.back().first][snake.back().second] = 0;
		snake.pop_back();
	}

	map[head.first + dy[now_dir]][head.second + dx[now_dir]] = 3;
	
	return 0;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	cin >> k;

	for (int i = 0; i < n+1; i++) {// 틀 만들기
		map[i][0] = 3;
		map[i][n+1] = 3;
		map[0][i] = 3;
		map[n + 1][i] = 3;
	}

	snake.push_front({ 1, 1 }); // 뱀 시작 오른쪽으로 갈것
	map[1][1] = 3;

	int app_y, app_x;
	for (int i = 0; i < k; i++) {
		cin >> app_y >> app_x;
		map[app_y][app_x] = 1; // 사과

	}
	cin >> l;

	string dir_L;

	int move_time = 0;
	for (int i = 0; i < l; i++) {
		cin >> move_time >> dir_L;
		
		while (move_time!= now_time) {// 시간이 아직 안됨
			
			if (update()) {
				cout << now_time;
				return 0;
			}
			

		}
	
		if (dir_L == "D") {// 오른
			if (now_dir == 0) {
				now_dir = 3;
			}
			else if (now_dir == 1) {
				now_dir = 2;
			}
			else if (now_dir == 2) {
				now_dir = 0;
			}
			else {
				now_dir = 1;
			}

		}
		else {
			if (now_dir == 0) {
				now_dir = 2;
			}
			else if (now_dir == 1) {
				now_dir = 3;
			}
			else if (now_dir == 2) {
				now_dir = 1;
			}
			else {
				now_dir = 0;
			}
		}
		//---------------방향결정

		if (update()) {
			cout << now_time;
			return 0;
		}
		
	}

	while (1) {
		if (update()) {
			cout << now_time;
			return 0;
		}
	}
	
	return 0;

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!