백준 3190:

1) 문제 분석

  조건만 잘 따져주면 크게 어려울 게 없는 문제이다.

  1. 뱀은 (0,0)에서 시작하며 길이는 1이고 오른쪽을 향한다
  2. 1초마다 몸길이를 늘려 머리를 다음칸에 위치 시킨다
     (1) 다음 칸에 사과가 있다면, 사과를 먹는다
     (2) 다음 칸에 사과가 없다면 몸길이를 줄여서 꼬리가 위치한 칸을 비운다.
    이 때, 뱀이 벽이나 자기자신과 부딪히면 게임이 끝나는데, 코드를 짜면서 처음에 실수했던 점은, 우선 머리가 먼저 다음 칸으로 나아간다는 것이다. 가령 머리가 이어지는 다음 칸에 꼬리가 위치해 있으면, 머리가 움직이는 동시에 꼬리도 움직여서 머리가 꼬리랑 안 부딪히는 게 아니라 머리가 먼저 앞으로 나가서 둘이 부딪히게 된다. 이 점을 염두해두면 코드 작성은 쉽다.

2) 알고리즘

  우선 2차원 정수 배열로 정사각 보드를 표현하고, 사과가 위치한 곳의 값을 2로 설정하기로 하였다. 그리고 뱀이 방향을 바꾸는 정보들(시간과 방향)은 입력 받아서 큐에 넣고 뱀이 초마다 움직일 때 마다 큐의 첫 번째 원소의 시간 값과 현재 시간 값을 비교하여 같다면 큐에서 원소를 뽑아내고 뱀의 이동 방향을 바꾸는 식으로 했다.
  뱀의 몸이 현재 위치한 좌표들을 저장하기 위해서 deque를 사용했는데 좌표들을 순서대로 저장하면서 앞에서는 push하고 뒤에서는 pop하는 동작이 필요했기 때문이다. 뱀이 움직일 때마다 deque의 front에 머리가 위치한 새로운 좌표가 추가되고 꼬리가 위치한 좌표(deque에서 마지막 좌표)는 사과의 유무에 따라 없앨 수도 남길 수도 있다. 가장 앞부분과 뒷부분의 두 좌표를 제외하고 중간값들은 뱀의 몸이 먼저 위치한 앞 칸을 그대로 따라가므로 수정해줄 필요가 없다.

3) 코드

#include <iostream>
#include <deque>
#include <queue>

using namespace std;

//changing directions
#define turn_left(n) (n=(n+3)%4)
#define turn_right(n) (n=(n+5)%4)

typedef pair<int,int> pos;     //positions of the snake
typedef pair<int,char> path;   //<sec, direction>: tells when the snake changes its direction

//game board
int board[100][100];
//N: size of the board  K: number of apples
int N, K;
//save positions where the snake's body is located
deque<pos> snake;
//current direction the snake is heading to
int dir;
//tells when the snake changes its direction
queue<path> moves;
//time it takes the game to finish
int total_t;

int main(){
    int i,j,turns;
    char c;
    bool crash;

    //get input from user
    cin >> N;
    cin >> K;

    //locate apples on the board
    for(int k=0; k<K; k++){
        cin >> i; cin >> j;
        board[i-1][j-1] = 2;
    }

    //direction changes
    cin >> turns;
    for(i=0; i<turns; i++){
        cin >> j; cin >> c;
        path temp = {j,c};
        moves.push(temp);
    }


    //snake starts moving at the upper-left corner
    pos temp = {0,0};
    snake.push_back(temp);

    total_t = 0;
    dir = 1;       //snake is heading toward the right
    crash = false;
    //repeat until the snake does not bump into itself or the wall
    while(!crash){
        //check if it's time for the snake to make a turn
        if(moves.front().first == total_t++){
            c = moves.front().second; moves.pop(); //remove the element from the queue
            if(c=='L') turn_left(dir);  //turn left
            else  turn_right(dir);      //turn right
        }

        //get the current position of the head
        pos head = snake[0];
        //move one block forward
        switch(dir){
            case 0: head.first--; break;   //upwards
            case 1: head.second++; break;  //rightwards
            case 2: head.first++; break;   //downwards
            case 3: head.second--; break;  //leftwards
            default: break;
        }
        //check if the snake hits the wall
        if(!(0<=head.first && head.first<N) || !(0<=head.second && head.second<N))
            break;
        //check itf the head hits its body
        for(auto it=snake.begin()+1; it!=snake.end(); ++it){
            if(head.first==it->first && head.second==it->second) {
                crash = true;
                break;
            }
        }
        //add new position of the head to the deque
        snake.push_front(head);

        //if there is an apple, the size increases
        if(board[head.first][head.second]==2)
            board[head.first][head.second] = 0;
        //if there is no apple, the tail also moves one block forward
        else
            snake.pop_back();
    }
    //print out the total time
    cout << total_t;
}