문제 링크: https://www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
<문제 풀이> deque(덱), 시뮬레이션
1. deque를 이용해서 뱀을 나타낸다
-> 뱀을 한 덩어리로 생각하지 말고 길이가 n이면 크기가 1인 뱀이 n개가 이어져있다고 생각하면
-> 각각의 뱀은 현재 자신의 위치와 방향을 가지고 있습니다.
2. deque로 뱀을 표현하면 이제 문제 그대로 구현하면 됩니다.
● 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
-> 현재 deque의 맨 마지막 뱀과 같은 방향을 가지면서 그 방향으로 1칸 이동한 좌표를 가진 뱀을 deque의 마지막에 push 한다.
● 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
-> 사과가 있는 좌표에 뱀이 있다는 표시를 해줍니다.
● 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
-> 맨 뒤에 꼬리만 자르면 되니깐 deque의 첫 번째 원소를 삭제합니다.
-> 이때 삭제한 뱀의 좌표에 뱀이 없다는 표시를 남겨줍니다.
종료 조건은 새로운 뱀이 벽을 만나거나 뱀을 만나면 종료하면 됩니다.
3. 근데 만약 현재 X초이고 X초가 끝난 뒤에 방향 변환 정보가 있다면
-> 새로운 뱀을 추가하기 전에 제일 뒤에 있는 뱀(머리)에 방향을 바꿔주면 됩니다.
방향 전환 및 표현은 소스 코드를 보시면 쉽게 이해하실 수 있습니다.
<C++ 소스 코드>
|
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
|
#include <iostream>
#include <deque>
using namespace std;
#define EMPTY 0
#define APPLE 1
#define SNAKE 2
enum {
LEFT,
RIGHT,
UP,
DOWN
};
const int dx[4] = {0, 0, -1, 1}; // LEFT, RIGHT, UP, DOWN
const int dy[4] = {-1, 1, 0, 0};
class body {
public:
int x;
int y;
int dir;
body(int x, int y, int dir) {
this->x = x;
this->y = y;
this->dir = dir;
}
};
int board[101][101];
char rotateInfo[10001];
int N;
void rotateLeft(body &b) {
if (b.dir == LEFT) {
b.dir = DOWN;
}
else if (b.dir == RIGHT) {
b.dir = UP;
}
else if (b.dir == UP) {
b.dir = LEFT;
}
else if (b.dir == DOWN) {
b.dir = RIGHT;
}
}
void rotateRight(body &b) {
if (b.dir == LEFT) {
b.dir = UP;
}
else if (b.dir == RIGHT) {
b.dir = DOWN;
}
else if (b.dir == UP) {
b.dir = RIGHT;
}
else if (b.dir == DOWN) {
b.dir = LEFT;
}
}
int move() {
int second = 0; // 현재 흐른 시간
board[1][1] = SNAKE; //맨위 맨좌측에서 시작
body b(1, 1, RIGHT); //뱀은 처음에 오른쪽을 향한다.
deque<body> dq;
dq.push_back(b);
while (true) {
auto head = dq.back();
if (rotateInfo[second]) { //second 초가 끝난 뒤에 방향 변환 정보가 존재하면
dq.pop_back();
if (rotateInfo[second] == 'L') {
rotateLeft(head);
dq.push_back(head);
}
else if (rotateInfo[second] == 'D') {
rotateRight(head);
dq.push_back(head);
}
}
second++;
int nx = head.x + dx[head.dir];
int ny = head.y + dy[head.dir];
body new_head(nx, ny, head.dir);
dq.push_back(new_head); // 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
if (nx <1 || ny <1 || nx > N || ny > N || board[nx][ny] == SNAKE) { //벽 또는 자기자신의 몸과 부딪히면
return second; //종료
}
if (board[nx][ny] == APPLE) { //만약 이동한 위치에 사과가 있다면
board[nx][ny] = SNAKE; //그 칸에 있던 사과가 없어진다.
}
else if (board[nx][ny] == EMPTY) { //만약 이동한 위치에 사과가 없다면
board[nx][ny] = SNAKE;
board[dq.front().x][dq.front().y] = EMPTY;
dq.pop_front(); // 몸길이를 줄인다.
}
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
int k; cin >> k;
while (k--) {
int r, c; cin >> r >> c;
board[r][c] = APPLE;
}
int L; cin >> L;
while (L--) {
int X;
char C;
cin >> X >> C;
rotateInfo[X] = C;
}
cout << move();
return 0;
}
|
cs |
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 16973번] 직사각형 탈출 (0) | 2022.01.31 |
|---|---|
| [백준 16932번] 모양 만들기 (0) | 2022.01.31 |
| [백준 2638번] 치즈 (0) | 2022.01.17 |
| [백준 16985번] Maaaaaaaaaze (0) | 2022.01.16 |
| [백준 14499번] 주사위 굴리기 (0) | 2022.01.15 |