[백준] #3190. 뱀

문제는 여기서 확인할 수 있다. BaekJoon #3190. 뱀

📌 POINT

• 조건

  뱀이 매 초마다 한 칸씩 움직일 때

  1. 벽이나 스스로의 몸에 부딪히지 않고
  2. 주어진 명령에 따라 방향을 바꾸며
  3. 사과를 먹을 때마다 꼬리가 연장되는

  조건을 갖고 얼마나 생존할 수 있는가

• 주의할 점

  1. deque와 board 두 가지 방법으로 뱀의 현재 위치를 저장한다. 이동할 때 둘 다 처리하는 걸 주의한다.
  2. 명령에 나온 시간 이후에도 뱀은 계속 움직인다. 종료조건을 시간에 두지 않는다. -> 명령 index가 넘쳐서 index out of range오류를 만나지 않도록 예외처리를 해주자.

🚀 풀이

1. snake 구조체를 주로 이용했다.

• deque<pos> body
  머리가 추가되고 꼬리는 제거되니까 queue 자료구조를 사용한다고 생각할 수 있다. 하지만 큐는 front의 정보만 확인 가능하다. 우리는 양방향에서 pos를 확인할 수 있어야 한다. 따라서 deque를 사용한다.

• int dir
  시작인 오른쪽을 0으로, 시계방향으로 +1 씩 지정한다.
  이때 움직일 때 nx = x + mx[dir]이 되기 때문에 mx[], my[]도 시계방향으로 만들어줘야한다.

• bool move()
  dir 방향으로 한칸 움직이고 사과가 없으면 꼬리를 지워준다.
  -> 이때 board와 snake.body 모두 신경써준다.

• void turn(int direction)
  지정 방향으로 dir 변수 값을 조절해준다.

struct snake {
    int dir = 0;
    deque<pos> body;
    
    private :
    // 벽이나 몸에 부딪히는지 확인
    bool bump(int x, int y, int n){
        if(x <= 0 || y <= 0 || x > n || y > n) return true;
        else if(board[x][y] == SNAKE) return true;
        else return false;
    }

    public :
    // 지정방향으로 이동했는지 리턴
    bool move(int n){
        pos head = body.front();
        int nx = head.x + mx[dir];
        int ny = head.y + my[dir];
        if(bump(nx, ny, n)) return false;

        // tail
        if(board[nx][ny] != APPLE){
            pos tail = body.back();
            board[tail.x][tail.y] = EMPTY;
            body.pop_back();
        }
        // head
        body.push_front(pos(nx, ny));
        board[nx][ny] = SNAKE;
        return true;
    }

    void turn(int direction){
        if(direction == RIGHT) {
            dir = (dir + 1) % 4;
        }
        else {
            dir--;
            if(dir < 0) dir += 4;
        }
        return;
    }
};

2. while문을 이용해서 전체 알고리즘 구성

• (1, 1) 위치에서 출발
  • clock ++
  • 뱀 이동
    • snake.move() == false이면 clock 리턴
  • clock이 명령의 시간과 일치하는지 확인
    • 일치하면 명령대로 방향 바꾸기 `snake.turn()
    • 명령을 하나 처리했으니까 order_index++

int game_on(int map_size, int &order_num, vector<order> &order_list){
    int game_clock = 0;
    int order_index = 0;
    snake sn;
    sn.body.push_back(pos(1, 1));
    board[1][1] = SNAKE;
    while(true){
        game_clock++;
        int is_ok = sn.move(map_size);
        if(!is_ok) return game_clock;
        if(order_index < order_num && game_clock == order_list[order_index].time){
            sn.turn(order_list[order_index].dir);
            order_index++;
        }
    }
}