[BOJ] 3190. 뱀

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define p pair<int,int>
using namespace std;

// 동 서 남 북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

/*
 Left : 0
 Right : 1
 [4] : 동 서 남 북
 [2] : 다음 방향 위치 Index
 
 ex) [1][0]은
 (1,1)위치에서 현재 동쪽을 바라보고 있으며
 Left Turn을 해야한다.
 그러면
 x = x + dx[2]
 y = y + dy[2]
 다음 위치는 (2,1)이 된다.
 */
int changeDir[4][2] = {
    {3,2},
    {2,3},
    {0,1},
    {1,0},
};


int map[105][105];
p turn_map[105][105];
int visit[105][105];
queue<p> q;

int n,k;
int t;

p tail_pos;
int tail_dir;

bool inRange(int x, int y){
    if( x < 1 || x > n || y < 1 || y > n)
        return false;
    return true;
}

void print(){
    for(int i=0; i<=n; i++)
        cout << i%10 << " ";
    cout << endl;
    
    for(int i=1; i<=n-25; i++){
        cout << i%10 << " " ;
        for(int j=1; j<=n; j++){
            if(visit[i][j] != 0)
                cout << visit[i][j] << " ";
            else
                cout << " " << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    t = 0;
    
    cin >> n >> k;
    
    for(int i=0; i<k; i++){
        int a,b;
        cin >> a >> b;
        map[a][b] = 1;
        visit[a][b] = 9;
    }
    
    int l;
    cin >> l;
    
    for(int i=0; i<l; i++){
        int a;
        char b;
        cin >> a >> b;
        /*
         Left : 0
         Right : 1
         */
        if( b == 'D') // 오른쪽
            q.push( p(a,1) );
        else
            q.push( p(a,0) );
    }
    tail_pos.first = 1;
    tail_pos.second = 1;
    tail_dir = 0;

    int x = 1;
    int y = 1;
    int dir = 0;
    
    while(1){
        visit[x][y] = 1;
//        cout << "time : " << t << endl;
//        cout << "Head : " << x << " " << y << endl;
//        cout << "Tail : " << tail_pos.first << " " << tail_pos.second << " " << tail_dir << endl;
//        print();
        if(!q.empty() && t == q.front().first){
            dir = changeDir[dir][q.front().second];
            q.pop();
            turn_map[x][y] = p(dir,turn_map[x][y].second + 1);
        }
        t++;
        x = x + dx[dir];
        y = y + dy[dir];
        if( visit[x][y] == 1 || ! inRange(x, y)){
            break;
        }
        
        // 사과가 있을 경우
        if(map[x][y] == 1){
            // 사과 없애기
            map[x][y] = 0;
            // 머리만 이동
        }
        else{ // 꼬리 이동 후 머리 이동
            
            // 가장 마지막 꼬리 영역 없애기
            visit[tail_pos.first][tail_pos.second] = 0;
            if(turn_map[tail_pos.first][tail_pos.second].second != 0){
                tail_dir = turn_map[tail_pos.first][tail_pos.second].first;
                turn_map[tail_pos.first][tail_pos.second].second--;
            }
            tail_pos.first += dx[tail_dir];
            tail_pos.second += dy[tail_dir];
        }
    }
    
    cout << t << endl;
    return 0;
}

#include<iostream>
#include<queue>
#define SIZE 101
#define EMPTY 0
#define APPLE 1
#define VISIT 2
using namespace std;
int N,K,L;
int arr[SIZE][SIZE];
queue< pair< int, int >>cmd;
int currentTime, currentDirection;
// 동 = 0 서 = 1 남 = 2 북 = 3
//[현재 방향] [D = 0 L = 1, D / L에 따른 다음 방향]
int dmove[4][2]={
    {2,3},
    {3,2},
    {1,0},
    {0,1}
};
int drow[4] = { 0,0,1,-1 };
int dcol[4] = { 1,-1,0,0 };
bool isOK(int row, int col)
{
    return (0 < row && row <= N && 0 < col && col <= N);
}
int snakeMove()
{
    queue< pair< int, int >>snake;
    snake.push({ 1, 1 });
    arr[1][1] = VISIT;
    int row = 1;
    int col = 1;
    while (1)
    {
        int cmdTime = cmd.front().first;
        int cmdDir = cmd.front().second;

        // 방향 전환
        if (cmdTime == currentTime)
        {
            cmd.pop();
            currentDirection = dmove[currentDirection][cmdDir];
        }
        currentTime++;
        row += drow[currentDirection];
        col += dcol[currentDirection];
        //기저 사례
        if (isOK(row, col) == false) break; //벽 피해야함
        if (arr[row][col] == VISIT) break; //몸통 피해야함
        
        /*
         사과가 없다면
         큐에서 가장 마지막에 있었던 위치 값을 pop 후
         그 위치에 더이상 꼬리가 없음을 표시한다.
         (= arr에서 해당 좌표를 EMPTY 처리한다.)
         */
        if (arr[row][col] == EMPTY)
        {
            int eraseRow = snake.front().first;
            int eraseCol = snake.front().second;
            arr[eraseRow][eraseCol] = EMPTY;
            snake.pop();
        }
        snake.push({ row,col });
        arr[row][col] = VISIT;
    }
    return currentTime;
}
int main()
{
    scanf("%d",&N);
    scanf("%d",&K);
    int a, b; char c;
    for (int i = 0; i < K; i++)
    {
        scanf("%d %d",&a,&b);
        arr[a][b] = APPLE;
    }
    scanf("%d",&L);
    for (int i = 0; i < L; i++)
    {
        scanf("%d %c",&a,&c);
        if (c == 'D')
            cmd.push({ a,0 });
        else if (c == 'L')
            cmd.push({ a,1 });
        else
            printf("error cmd");
    }
    printf("%d", snakeMove());
    return 0;
}