[백준] 3190번 뱀

3190번 뱀

---

1. 이해하기
   • 뱀의 처음 시작 위치는 맨위 맨좌측, 길이는 1, 오른쪽을 보고있다.
   • 뱀은 몸길이를 먼저 늘려 머리를 다음칸에 위치시킨다.
     • 이동한 칸에 사과가 있다면, 사과가 없어지고 꼬리는 그대로이다.
     • 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 있던 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
   • 게임이 끝나는 조건이 뱀이 벽 혹은 몸통에 부딪히면 일때 이 게임이 몇 초에 끝나는지를 계산하는 문제.
   • 뱀을 이동시키면서 상태를 보는 시뮬레이션 문제.

---

2. 구현하기

   • 1초마다 뱀의 움직임 상태 반환

     • 이동에 성공했으면 true를 반환, 실패했으면 false를 반환
     • 실패는 몸통에 닿았거나 벽에 부딪혔을 때

   • 뱀의 몸통 상태는 queue에 넣어서 관리

     • 움직였을 때 사과가 있으면 꼬리 그대로, 없으면 꼬리 삭제.

     bool move(int& hx, int& hy, int dir) {
         int nhx = hx+dx[dir], nhy = hy+dy[dir];
         if(nhx < 0 or nhx >= N or nhy < 0 or nhy >= N) return false;
         if(snake[nhx][nhy]) return false;
         snake[nhx][nhy] = true; snake_inf.push({nhx,nhy});
         if(map[nhx][nhy] == 1) {
             map[nhx][nhy] = 0;
         } else {
             if(!snake_inf.empty()) {
                 int x = snake_inf.front().x, y = snake_inf.front().y; snake_inf.pop();
                 snake[x][y] = false;
             }
         }
         hx = nhx; hy = nhy;
         return true;
     }

---

3. 전체 구현

   #include <iostream>
   #include <queue>
   using namespace std;
   struct Point{
       int x,y;
   };
   int map[100][100];
   bool snake[100][100];
   char t[10001];
   queue<Point> snake_inf;
   int dx[] = {0,1,0,-1};
   int dy[] = {1,0,-1,0};
   int N;
   
   bool move(int& hx, int& hy, int dir) {
       int nhx = hx+dx[dir], nhy = hy+dy[dir];
       if(nhx < 0 or nhx >= N or nhy < 0 or nhy >= N) return false;
       if(snake[nhx][nhy]) return false;
       snake[nhx][nhy] = true; snake_inf.push({nhx,nhy});
       if(map[nhx][nhy] == 1) {
           map[nhx][nhy] = 0;
       } else {
           if(!snake_inf.empty()) {
               int x = snake_inf.front().x, y = snake_inf.front().y; snake_inf.pop();
               snake[x][y] = false;
           }
       }
       hx = nhx; hy = nhy;
       return true;
   }
   
   int main() {
       int K;
       cin >> N >> K;
       for(int i = 0; i < K; i++) {
           int x,y;
           cin >> x >> y;
           x-=1; y-=1;
           map[x][y] = 1;
       }
       int L;
       cin >> L;
       for(int i = 0; i < L; i++) {
           int s;
           char d;
           cin >> s >> d;
           t[s] = d;
       }
       int cur_dir = 0, cx = 0, cy = 0;
       snake[cx][cy] = true; snake_inf.push({cx,cy});
       int ans = 0;
       while(1) {
           ans += 1;
           if(!move(cx,cy,cur_dir)) break;
           if(t[ans] == 'D') {cur_dir = (cur_dir+1)%4;}
           else if(t[ans] == 'L') {cur_dir = (cur_dir-1<0)?3:cur_dir-1;}
       }
       cout << ans << '\n';
       return 0;
   }