반응형
https://www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
[ 문제풀이 ]
덱(deque)이라는 자료구조를 활용하여 문제를 풀었습니다.
1. 사과의 위치와 시간에 따른 방향 정보를 입력받습니다.
2. 덱을 활용하여 머리와 꼬리의 정보를 저장합니다.
3. 사과를 먹으면 꼬리를 그대로 두고, 사과를 먹지 않는다면 꼬리를 덱에서 빼줍니다.
4. 벽이나 몸에 부딪히면 현재 시간을 출력해주고 종료합니다.
5. 정보를 바탕으로 배열에 값을 저장해줍니다.
[ 소스 코드 ]
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 | #include<iostream> #include<deque> using namespace std; struct pos { int y; int x; }; int N, K, L; int arr[101][101]; //보드 int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,1,0,-1 }; int dir = 1; deque<pos> dq; int cnt; char direction[10001]; //시간 X이후 움직일 방향 저장할 배열 int main() { scanf("%d %d", &N, &K); for (int i = 0; i < K; i++) { int a, b; scanf("%d %d", &a, &b); arr[a][b] = 1; } scanf("%d", &L); for (int i = 0; i < L; i++) { int a; char b; scanf("%d %c", &a, &b); direction[a] = b; } dq.push_back({ 1,1 }); arr[1][1] = 2; while (1) { int fy = dq.front().y; //머리 int fx = dq.front().x; int by = dq.back().y; //꼬리 int bx = dq.back().x; int yy = fy + dy[dir]; //이동할 좌표 int xx = fx + dx[dir]; cnt++; if (arr[yy][xx] == 2 || yy<1 || yy>N || xx<1 || xx>N) { //몸통이거나 벽이라면 printf("%d", cnt); return 0; } if (arr[yy][xx] != 1) { //사과를 먹지 않으면 arr[by][bx] = 0; dq.pop_back(); } arr[yy][xx] = 2; dq.push_front({ yy,xx }); if (direction[cnt] == 'L') { dir--; } else if (direction[cnt] == 'D') { dir++; } if (dir < 0) { dir = 3; } if (dir > 3) { dir = 0; } } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 11727번 - 2xn 타일링 2 (C++) (0) | 2022.08.17 |
|---|---|
| [ 백준 ] 14499번 - 주사위 굴리기 (C++) (0) | 2022.08.16 |
| [ 백준 ] 7576번 - 토마토 (C++) (0) | 2022.08.14 |
| [ 백준 ] 16928번 - 뱀과 사다리 게임 (C++) (0) | 2022.08.13 |
| [ 백준 ] 9465번 - 스티커 (C++) (0) | 2022.08.12 |