[백준 3190] 뱀 (Simulation, Deque) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
 
int N;
int appleNum;
int rotateNum;
int rotateIdx;
int time;
 
vector<pair<int, int>> apple;
vector<pair<int, char>> rotate;
deque<pair<int, int>> snake;;
 
int dx[4] = {-1, 0, 1, 0}; // 북, 동, 남, 서 
int dy[4] = {0, 1, 0, -1}; // 북, 동, 남, 서 
 
int safe(int x, int y)
{
    if(x >= 1 && y >= 1 && x <= N && y <= N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int check_snake(int x, int y)
{
    for(int i = 0; i < snake.size(); i++)
    {
        if(x == snake[i].first && y == snake[i].second)
        {
            return 0;
        }
    }
    
    return 1;
} 
 
void solve(int x, int y, int dir)
{    
    while(1)
    {
        // 시간 증가 
        time++; 
        
        // 뱀의 머리 좌표 
        x += dx[dir];
        y += dy[dir];
        
        if(safe(x, y) == 1 && check_snake(x, y) == 1)
        {         
            // 몸길이 증가
            snake.push_front({x, y});
        
            // 사과 체크 
            bool eat_apple = false;
            
            for(int i = 0; i < apple.size(); i++)
            {
                if(x == apple[i].first && y == apple[i].second)
                { 
                    eat_apple = true;
                    apple.erase(apple.begin()+i);
                    break;        
                }
            }
            
            // 사과 못먹었으면 몸길이 감소(꼬리 자름) 
            if(eat_apple == false)
            {
                snake.pop_back();
            }
        }
        // 벽에 닿거나 자신의 몸에 닿으면 게임종료 
        else
        {
            return;
        }
        
        // 방향 전환 
        if(time == rotate[rotateIdx].first)
        {
            // 왼쪽 90도 
            if(rotate[rotateIdx].second == 'L')
            {
                dir = (dir+3) % 4;
            }
            // 오른쪽 90도 
            else
            {
                dir = (dir+1) % 4;
            }
            
            rotateIdx++;
        }    
    }
}
 
int main(void)
{
//    freopen("B3190_input.txt", "r", stdin);
    
    cin >> N;
    
    cin >> appleNum; 
    for(int i = 0; i < appleNum; i++)
    {
        int x, y;
        cin >> x >> y;
        
        apple.push_back({x, y});
    }
    
    cin >> rotateNum;
    for(int i = 0; i < rotateNum; i++)
    {
        int time;
        char dir;
        cin >> time >> dir;
        
        rotate.push_back({time, dir});
    }
    
    snake.push_back({1, 1});
    solve(1, 1, 1);
    
    cout << time; 
    
    return 0;
}