포스트

3190 뱀(C++)

게시
By Dukgukim

뱀 게임. 빡구현 문제

한창 SSAFY에서 알고리즘 공부할때 풀었던거같은데 재도전해봤다

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

1. 문제

간단 설명

매초마다 다음 과정이 반복됨

  1. 뱀은 몸 길이를 늘려 머리를 다음 칸에 위치시킴

  2. 벽이나 자기자신의 몸과 부딛친다면 게임 종료

  3. 이동한 칸에 사과가 있다면, 그 칸의 사과를 먹고 꼬리는 움직이지 않는다(늘어남)

  4. 이동한 칸에 사과가 없다면, 몸 길이를 줄여 꼬리가 위치한 칸을 비운다. (유지)

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

게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다.

뱀은 처음에 오른쪽을 향한다

2. 문제 분석

  • 게임 종료 조건

게임 종료 조건이 벽에 박아 죽거나, 자기 자신을 물어서 죽는 경우밖에 없음

사과를 다 먹어서 게임이 종료되는 조건은 없다

  • 뱀이 회전하는 타이밍

게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다

라고 설명함. 즉 3 D라고 주어지고, 2초에 오른쪽으로 진행하고 있다면

3초에는 오른쪽으로 진행하고, 3초가 끝나는 순간 아래쪽으로 진행한다는 것이다.

그 방향으로 진행하는 것이 아닌 회전하는거임!

  • 예시 2번 설명

image

0초. 뱀의 초기 머리 위치는 (1,1), 길이는 1, 오른쪽을 향함

image

1초. 뱀의 머리 위치는 (1,2), 사과를 먹어 길이는 2, 오른쪽을 향함

image

4초. 뱀의 머리 위치는 (1,4), 길이는 4, 오른쪽

image

8초. 뱀의 머리 위치는 (1,9), 길이는 4, 8 D로 오른쪽으로 회전함

image

10초. 뱀의 머리 위치는 (3,9), 길이는 4, 10 D로 우회전

image

11초. 뱀의 머리 위치 (2,8), 길이 4, 11 D로 우회전

image

13초. 뱀의 머리 위치 (1,8), 길이 4, 13 L로 좌회전

image

21초 경과 머리가 맵 밖으로 떨어져서 종료

필요변수

맵크기 int N (2<=N<=100)

사과의 개수 int K (0 ≤ K ≤ 100)

int map[101][101];

입력받으면서 사과는 따로 저장하지 않고 맵에 1로 표시한다

뱀이 머리가 사과의 좌표와 일치하는지 체크하려면

별도의 사과를 저장한 벡터를 순회하면서 비교하는 것 보다는

맵의 인덱스를 참조하는게 더 빠를 것 같아 맵을 사용함

뱀 구조체 Snake

  • 현재 뱀의 진행 방향을 저장하는 변수 char face
  • 뱀의 몸통들의 좌표를 저장할 deque body. 몸과 머리의 충돌을 확인하기 위해 필요하다
    • 머리를 앞에 넣어줘야하므로 벡터가 아닌 덱을 이용함
  • void Move() 뱀을 이동시키는 함수

매초 seconds; 사과를 모두 먹으면 종료하고 이값을 출력.

방향 변환 정보의 개수 M

  • 문제를 잘 읽자 왼쪽 오른쪽밖에 명령어가 없음
    • 뱀의 머리가 상하좌우가 주어지는게 아니라, 현재 보고있는 방향에서 왼쪽 오른쪽 90도 회전밖에 없음

주의점

  • 문제를 잘 읽을 것. 방향이 주어지는게 아니라, 좌회전, 우회전이 주어진다
  • 구현 과정을 잘 설계하고 코딩할 것
  • 예시를 잘 이해해야 시간을 언제 증가시키는지 이해할 수 있음
  • 좌표가 (0,0) 이 시작이 아니라 (1,1) 시작이다

알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1. 맵크기 N, 사과 개수 K입력받기
2. K개의 사과의 좌표를 입력받아 map에 1로 표시해둔다
3. M개의 방향 변환 정보들을 입력받아 posInfo 배열에 저장해둔다
-- 여기서부터 루프---
4. 뱀의 종료 조건이 활성화 될때까지 시간초를 증가시키면서 뱀을 이동시킨다
    4-1. 방향 변환 정보가 있다면, 가장 맨 앞의 정보를 확인한다
        - 현재 시간초와 정보의 시간초가 같다면, 뱀의 고개를 돌린다.
    4-2. 뱀을 움직인다
        4-2-1. 다음 움직일 좌표를 확인한다. (머리 방향으로 1 진행한 좌표를 체크)
        4-2-2. 만약 맵 밖으로 나갔다면 종료 조건 활성화
        4-2-3. 자기 몸하고 부딛쳤다면 종료 조건 활성화
        4-2-4. 다음 움직일 좌표로 머리를 이동시킨다. (덱의 맨 앞에 삽입)
        4-2-5. 머리 좌표에 사과가 있다면, 맵에 먹었다고 표시한다
        4-2-6. 머리 좌표에 사과가 없다면, 꼬리를 제거한다. (덱의 맨 뒤를 pop)
    4-3. 시간을 1초 증가시킨다
    4-4. 종료 조건이 활성화 되었는지 체크

5. 시간초를 출력하고 종료한다

3. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int N, K, M;
int map[101][101];

struct PosInfo {
	int time;
	char dir;
};
deque<PosInfo> posInfo;

struct Snake {
	deque<pair<int, int>> body = { {1,1} };
	char face ='R';
	bool gameover_flag = false;

	// 뱀을 보고있는 방향으로 이동시키는 함수
	void Move() {
		int dy = body[0].first, dx = body[0].second;
		if (face == 'U') {
			dy -= 1;
		}
		else if (face == 'D') {
			dy += 1;
		}
		else if (face == 'L') {
			dx -= 1;
		}
		else if (face == 'R') {
			dx += 1;
		}
		// 맵 밖으로 나갔는지 확인d
		if (dy < 1 || dx < 1 || dy > N || dx > N) {
			gameover_flag = true;
		}
		// 자기 몸하고 부딛쳤는지 확인
		for (pair<int, int> e : this->body) {
			if (dy == e.first && dx == e.second) {
				gameover_flag = true;
			}
		}

		this->body.push_front({ dy, dx }); // 머리 이동

		// 사과 먹었는지 체크 
		if (map[this->body[0].first][this->body[0].second] == 1) {
			map[this->body[0].first][this->body[0].second] = 0;
			// 사과를 먹었다면 따로 꼬리를 뺴지 않고 맵만 0으로 갱신한다
		}
		// 만약 사과가 없다면 꼬리 뺴기
		else if (map[this->body[0].first][this->body[0].second] != 1) {
			this->body.pop_back();
		}

	}
};

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;

	// 사과 정보 입력받기
	cin >> K;
	for (int i = 0; i < K; i++) {
		int yy, xx;
		cin >> yy >> xx;
		map[yy][xx] = 1;
	}

	// 방향 변환 정보 입력받기
	cin >> M; posInfo.resize(M);
	for (int i = 0; i < M; i++) {
		cin >> posInfo[i].time >> posInfo[i].dir;
	}

}

int main() {
	// 1. 입력받기
	Input();

	Snake snake;
	int seconds = 0;
	while (1) {
		// 뱀의 방향 변환 정보에 주어진 시간이 되면 정보 갱신
		if (!posInfo.empty() && seconds == posInfo[0].time) {
			if (posInfo[0].dir == 'D') {
				if (snake.face == 'U') snake.face = 'R';
				else if (snake.face == 'R') snake.face = 'D';
				else if (snake.face == 'D') snake.face = 'L';
				else if (snake.face == 'L') snake.face = 'U';
			}
			else if (posInfo[0].dir == 'L') {
				if (snake.face == 'U') snake.face = 'L';
				else if (snake.face == 'R') snake.face = 'U';
				else if (snake.face == 'D') snake.face = 'R';
				else if (snake.face == 'L') snake.face = 'D';
			}
			posInfo.pop_front();
		}

		snake.Move();
		seconds++;
		if (snake.gameover_flag == true) break;
	}

	cout << seconds;

	return 0;
}

이전에 했던 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int n, k;
int map[101][101]; // 1<= y,x <= 100 이용, 0: 비어있음, 1: 뱀, 2: 사과

// →, ←, ↑, ↓
int directY[4] = {0, 0, -1, 1};
int directX[4] = {1, -1, 0, 0};

vector< pair<int, char> > cmd;

void input() {
	// freopen_s(new FILE*, "test.txt", "r", stdin);

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int y, x;
		cin >> y >> x;
		map[y][x] = 2;
	}

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int cnt;
		char ch;
		cin >> cnt >> ch;
		cmd.push_back(make_pair(cnt, ch));
	}
}


// 현재 어느 방향을 보고있는지 보고, ch에 따라 고개를 돌리는 함수
int turn_direction(int face, char ch) {
	if (ch == 'L') {
		if (face == 0) return 2;
		else if (face == 1) return 3;
		else if (face == 2) return 1;
		else if (face == 3) return 0;
	}
	else if (ch == 'D') {
		if (face == 0) return 3;
		else if (face == 1) return 2;
		else if (face == 2) return 0;
		else if (face == 3) return 1;
	}

}


int main() {
	
	input();

	deque< pair<int, int> > snake; // 뱀의 현재 위치를 저장하는 덱

	int sec = 0;
	int cnt = 0;

	// 뱀 (1,1) 에서 시작	
	int y = 1;
	int x = 1;
	int face = 0; // 뱀이 보는 방향 // →, ←, ↑, ↓
	map[y][x] = 1;
	snake.push_back(make_pair(y, x)); 


	while (1) {
		sec++;

		int dy = y + directY[face];
		int dx = x + directX[face];

		if (dy < 1 || dx < 1 || dy > n || dx > n) break; // 1. 벽에 닿은 경우
		else if (map[dy][dx] == 1) break; // 2. 자기 몸과 닿은경우
		else if (map[dy][dx] == 0) { // 3. 비어있는 경우

			map[dy][dx] = 1; // 머리이동
			pair<int, int> tail = snake.back();
			snake.pop_back();
			
			map[tail.first][tail.second] = 0; // 꼬리 땡기기
			snake.push_front(make_pair(dy, dx)); // 머리를 큐에 삽입

		}
		else if (map[dy][dx] == 2) { // 4. 사과가 있는 경우

			map[dy][dx] = 1; // 머리이동

			snake.push_front(make_pair(dy, dx)); // 머리를 큐에 삽입

		}

		// 명령어가 남아있는지 확인
		if (cnt < cmd.size()) {
			if (sec == cmd[cnt].first) {

				if (cmd[cnt].second == 'D') {
					face = turn_direction(face, 'D');
				}

				else if (cmd[cnt].second == 'L') {
					face = turn_direction(face, 'L');
				}

				cnt++;
			}
		}
		y = dy;
		x = dx;
	}

	cout << sec << endl;

	return 0;
}
Algorithm, Problem Solving
impl
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.