[URL]
https://www.acmicpc.net/problem/3190
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따
www.acmicpc.net
[풀이 과정]
* 시뮬레이션
뱀의 머리랑 꼬리에만 신경 쓰자
뱀의 전체는 check[][]배열에 넣어주자. : 이동 가능한지 판단
1) input()
int rota[10001]; // 1: L 왼쪽 90회전, 2: R 오른쪽 90회전 , 0이면 회전X
2) while(1)
sec증가, 뱀의 머리가 갈 수 있는지 판단,
가능하면 move(), 불가능하면 break;
move()
1. 사과가 있는 경우
// 사이즈 증가
// 뱀 머리 벡터에 저장
// 뱀 현재 위치 판단
// 먹은 사과 지워주고
// 뱀 머리 이동
2. 사과가 없는 경우
// 뱀 머리 벡터에 저장
// 뱀 현재 위치 판단
// 뱀 꼬리쪽 이동, 현재 위치 판단
// 꼬리 벡터에서 지워주기
// 뱀 머리 이동
[소스 코드]
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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | #include <stdio.h> #include <vector> using namespace std; struct Snake { int x = 1; int y = 1; int dir = 3; // 오른쪽 방향 시작 int size = 1; }; Snake s1; vector <pair <int, int>> v; int N; int K; int L; int map[101][101]; bool check[101][101]; int rota[10001]; // 1: L 왼쪽 90회전, 2: R 오른쪽 90회전 int dx[] = { -1, 1, 0, 0 }; // 0상 1하 2좌 3우 int dy[] = { 0, 0, -1, 1 }; void input() { scanf("%d", &N); scanf("%d", &K); for (int i = 0; i < K; i++) { int x, y; scanf("%d", &x); scanf("%d", &y); map[x][y] = 1; } scanf("%d\n", &L); for (int i = 0; i < L; i++) { int tempX; char tempC; scanf("%d %c", &tempX, &tempC); if (tempC == 'L') { rota[tempX] = 1; } if (tempC == 'D') { rota[tempX] = 2; } } check[1][1] = true; // 맨 처음 뱀의 위치 설정 v.push_back(make_pair(1, 1)); // 맨 처음 뱀의 위치 벡터에 저장 } bool isPossible() { bool flag = false; int nx = s1.x + dx[s1.dir]; int ny = s1.y + dy[s1.dir]; if (nx >= 1 && nx <= N && ny >=1 && ny <= N) { if (check[nx][ny] == false) { flag = true; } } return flag; } void move() { int nx = s1.x + dx[s1.dir]; int ny = s1.y + dy[s1.dir]; if (map[nx][ny] == 1) // 다음 뱀 헤드가 사과인 경우 { s1.size++; // 사이즈 증가 v.push_back(make_pair(nx, ny)); // 뱀 머리 벡터에 저장 check[nx][ny] = true; // 뱀 현재 위치 판단 map[nx][ny] = 0; // 먹은 사과 지워주고 s1.x = nx; // 뱀 머리 이동 s1.y = ny; } else // 다음 뱀 헤드가 사과가 아닌 경우 { v.push_back(make_pair(nx, ny)); // 뱀 머리 벡터에 저장 check[nx][ny] = true; // 뱀 현재 위치 판단 check[v[0].first][v[0].second] = false; // 뱀 꼬리쪽 이동, 현재 위치 판단 v.erase(v.begin()); // 꼬리 벡터에서 지워주기 s1.x = nx; // 뱀 머리 이동 s1.y = ny; } } int main() { input(); int sec = 0; while (true) { sec++; if (isPossible()) // 벽 아니고 본인 아닐 때 가능! { move(); // 가능하면 이동! } else { break; // 아닐 경우 이동 불가 탈출 } // 해당 초에 회전 if (rota[sec] != 0) { if (rota[sec] == 1) { if (s1.dir == 0) { s1.dir = 2; } else if (s1.dir == 1) { s1.dir = 3; } else if (s1.dir == 2) { s1.dir = 1; } else if (s1.dir == 3) { s1.dir = 0; } } else if (rota[sec] == 2) { if (s1.dir == 0) { s1.dir = 3; } else if (s1.dir == 1) { s1.dir = 2; } else if (s1.dir == 2) { s1.dir = 0; } else if (s1.dir == 3) { s1.dir = 1; } } } } printf("%d\n", sec); return 0; } | cs |
'Algorithm > 백준' 카테고리의 다른 글
[BOJ] - 2468. 안전 영역 (0) | 2019.08.20 |
---|---|
[BOJ] - 17281. 야구 (0) | 2019.08.13 |
[BOJ] - 17143. 낚시왕 (0) | 2019.07.31 |
17140. - 이차원 배열과 연산 (0) | 2019.07.16 |
[BOJ] - 16236. 아기 상어 (0) | 2019.07.10 |