https://www.acmicpc.net/problem/3190
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따
www.acmicpc.net
이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.
이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.
(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다
|
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
|
#include <iostream>
#include <vector>
using namespace std;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int n, k;
//사과의 좌표를 저장
bool apple[100][100];
//머리가 위치한 시간을 저장
int headtime[100][100];
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cin >> n >> k;
//사과정보 저장
int ax, ay;
for (int i = 0; i < k; i++) {
cin >> ax >> ay;
apple[ax - 1][ay - 1] = true;
}
int l;
cin >> l;
int t;
char c;
//방향 회전 정보를 저장
vector<pair<int, char>> vt;
for (int i = 0; i < l; i++) {
cin >> t;
cin >> c;
vt.push_back(make_pair(t,c));
}
int time = 0;
//방향 회전정보를 이용하기 위한 인덱스
int index = 0;
//초기 방향
int dir = 0;
//초기 길이
int len = 1;
//초기 위치는 좌측 맨위쪽
int x = 0;
int y = 0;
while (true) {
//먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
time++;
len += 1;
int nx = x + dx[dir];
int ny = y + dy[dir];
//벽에 부딪힘
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
//몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
//이동한 칸에 현재 시간을 저장
headtime[nx][ny] = time;
//사과가 있는지 검사
if (apple[nx][ny]) {
apple[nx][ny] = false;
}
else {
len -= 1;
}
//l번만큼 방향이동을 한다.
if (index < l) {
//현재시간이 방향을 회전해야하는 시간이다
if (time == vt[index].first) {
if (vt[index].second == 'D') {
dir = (dir + 1) % 4;
}
else if (vt[index].second == 'L') {
dir = (dir + 3) % 4;
}
//방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
index++;
}
}
//현재 좌표를 머리가 이동한 칸의 좌표로 변경
x = nx;
y = ny;
}
cout << time << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2234. 성곽 (0) | 2019.08.13 |
|---|---|
| [BOJ] 11559. Puyo Puyo (0) | 2019.08.08 |
| [BOJ] 15683. 감시 (0) | 2019.08.05 |
| [BOJ] 14500. 테트로미노 (0) | 2019.08.04 |
| [BOJ] 14499. 주사위 굴리기 (0) | 2019.08.04 |