문제 URL : www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
문제 접근법 :
이것만 이해하시면됩니다. 1초동안 뱀의 머리가 먼저 움직여야하고
꼬리는 움직이거나 움직이지 않는다.
뱀의 머리와 꼬리가 y,x라는 좌표에 있고 한칸 움직일때 y,x+1로 움직였다고 가정한다면
머리가 먼저 움직인다면 y,x+1의 위치에있고 꼬리가 움직이기전이니 y,x입니다. 이때는 잠시 몸의길이가 일시적으로 증가했다는것을 알수있죠? 그치만 그머리위치가 사과가 있다면 꼬리는 움직이지 않으니 정상적으로 몸의길이가 증가되도록 시키는겁니다. 만약 사과가 없다면 꼬리도 x,y+1로 움직이고 몸의길이가 다시 줄어들겁니다.
이런식으로 문제조건대로 해주면 됩니다. 먼저 2가지를 그림으로 표현해드릴게요
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
위에 파란색원은 머리이고 보라색원은 꼬리입니다.
그리고 2번째 조건
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
이건 위의 따로 그림없이 머리만 꼬리만 움직이지 않는상태니 위의 그림에서 0.5초만 지난 상태와 같습니다.
그럼문제는 저렇게 움직일때 뱀의 몸을 어떻게 표현할까요??
간단합니다. 머리가 움직이는 길을 1로채워주고 꼬리가 움직이는 길을 0으로 채워주면 됩니다. 즉
머리가 움직일때 1을 만난다면 자신의 몸과 부딪히는걸 표현이가능합니다.
이런식으로 움직이게되면 머리의 방향과 꼬리의 방향을 가져야하고 서로 다른 방향으로 움직임또한 표현이 가능합니다.
그럼 코드를 보여드리겠습니다.
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <queue>
using namespace std;
int n, k,l;
int map[101][101]; //뱀의 몸통을 표시함
int apple[101][101];//사과의 위치
int dir[26];
int changeDir[10001]; //초마다 왼쪽또는 오른쪽으로 방향을 바꿔야합니다.
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
struct snake {
int hy, hx, ty, tx, hdir, tdir; //머리와 꼬리 머리방향 꼬리방향
int bodysize; //머리와 꼬리는 처음에 부터있고 몸통의 길이는 0 사과를먹으면 증가함
snake() {
hy = hx = ty = tx = hdir = tdir = 1;
bodysize = 0;
}
};
bool isrange(int y, int x) {
return 1 <= y && y <= n && 1 <= x && x <= n;
}
void input() {
cin >> n >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
apple[a][b] = 1;
}
cin >> l;
for (int i = 0; i < l; i++) {
int a;
char b;
cin >> a >> b;
changeDir[a] = b;
}
}
void solve() {
int cnt = 0;
snake s;
while (true) {
cnt++;
int ny = s.hy + dy[s.hdir]; //머리를 움직여본다
int nx = s.hx + dx[s.hdir];
if (!isrange(ny, nx)) //벽에 부딪히거나
break;
if (map[ny][nx])//자신의 몸에 부딪힌다면 종료
break;
map[ny][nx] = 1; //머리가가는곳을 남김 이게 자신의 몸
s.hy = ny;
s.hx = nx;
if (changeDir[cnt])//이때초에 방향을바꾸고 다음초부터 그방향대로움직임
s.hdir = ((s.hdir + 4) + dir[changeDir[cnt] - 'A']) % 4;
if (apple[ny][nx]) {//사과가 있다면 몸통의 길이만 증가시킴
apple[ny][nx] = 0;//사과를 먹었다는것을 표시
s.bodysize++;
}
else {
map[s.ty][s.tx] = 0;//꼬리도 따라가야하니 몸통을 줄임
s.ty += dy[s.tdir];
s.tx += dx[s.tdir];
if (changeDir[cnt - s.bodysize])//머리가 움직인대로 똑같이 움직여야함 머리랑 똑같이 움직였으니 꼬리가 자신의 몸에 부딪히거나 벽에 부딪히는일은 없음
s.tdir = ((s.tdir + 4) + dir[changeDir[cnt - s.bodysize] - 'A'])%4;
}
}
cout << cnt << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
dir['L' - 'A'] = -1;
dir['D' - 'A'] = 1;
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 혹은 질문 혹은 다른아이디어든 언제든지 댓글 이용부탁드립니다.
'백준' 카테고리의 다른 글
| 백준 1806 부분합 (0) | 2021.02.15 |
|---|---|
| 백준 20057 마법사 상어와 토네이도 (0) | 2021.02.10 |
| 백준 1525 퍼즐 (0) | 2021.01.01 |
| 벡즌 1929 소수 구하기 (0) | 2021.01.01 |
| 백준 16938 캠프 준비 (0) | 2020.12.31 |
