/* 사과를 먹으면 뱀 길이가 늘어납니다. 뱀이 기어다니다 벽 또는 몸과 부딪히면 게임이 끝납니다. 엔엔 정사각 보드위에서 진행됩니다. 몇몇 칸에 사과, 보드의 상화좌우 끝에 벽이 있습니다. 뱀은 맨위 맨 좌측 뱀의 길이는 1 입니다. 오르쪽을 향합니다. 몸길이를 늘려 머리를 다음칸에 위치. 이프 이동한칸 사과 있으면, 그 칸에 있던 사과없어지고 꼬리는 그대로 엘스 사과가 없으면, 몰길이르 줄여 꼬리를 위치한 칸을 비워줍니다. 그 결과 사과의 위치와 뱀의 이동경로가 주어질 때 게임이 몇 초 후에 끝나는지 계산 뱀의 길이나, 위치를 어떻게 저장해야하는지. */ #include <iostream> #include <vector> #include <queue> #define SIZE 10 using namespace std; int N, K, L, X, C, a_x, a_y, d, x, y, nx, ny, sec; int dx[] = { 0,0,1,-1 }; // 동 서 남 북 int dy[] = { 1,-1,0,0 }; int map[SIZE][SIZE]; int dir_x; char dir_y; struct dir_info{ int x; char y; }; struct snake_pos { int x, y; }; queue<dir_info> que; queue<snake_pos> snake; void problemIn() { cin >> N >> K; for (int i = 0; i < K; i++) { cin >> a_x >> a_y; map[a_x - 1][a_y - 1] = 2; // apple -> 2 } cin >> L; for (int i = 0; i < L; i++) { cin >> dir_x >> dir_y; que.push({ dir_x, dir_y }); } } int turn_right(int dir) { if (dir == 0) return 2; else if (dir == 1) return 3; else if (dir == 2) return 1; else return 0; } int turn_left(int dir) { if (dir == 0) return 3; else if (dir == 1) return 2; else if (dir == 2) return 0; else return 1; } void solve() { x = y = 0; d = 0; while (1) { // 사과를 발견하거나, 초 == 큐의 첫번째 엑스와 같을때 map[x][y] = 1; snake.push({ x,y }); nx = x + dx[d]; ny = y + dy[d]; //snake_die check if (map[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= N || ny >= N) { break; // snake die }
if (nx >= 0 && ny >= 0 && nx < N && ny < N) { sec++; if (map[nx][ny] == 0){ // 단순한 길이면 그냥 x,y 이동과 벡터 이동 map[snake.front().x][snake.front().y] = 0; // 뱀 이동 snake.pop(); x = nx; y = ny; } else if (map[nx][ny] == 2) { // 사과를 먹었으므로 그곳도 1로 변경, 이전 값은 그대로, map[nx][ny] = 1; x = nx; y = ny; } } // dir_info if (sec == que.front().x) { if (que.front().y == 'D') { d = turn_right(d);} else d = turn_left(d); que.pop(); } } } int main(void) { problemIn(); solve(); cout << sec + 1 << endl; return 0; } |
백준 뱀 시뮬레이션 여기서 보면 방향에 대한 오류때문에 처음에 풀이가 틀렸습니다. 다른 테스트케이스를 디버깅하면서 돌린 이후에 찾을 수 있었습니다. 그리고, 다른 것은 뱀이 어떻게 이동하는지를 담은 큐를 만드는 것이 문제였습니다. 이전에 풀이에 대한 아이디어가 남아있어서 그것을 구현했지만, 처음 보면 당황할 문제일 것 같습니다. 큐가 아닌 벡터의 사용법이나 스택에 대한 사용법도 어느정도 익혀두면 좋을 것 같습니다. |