[백준] 3190 : 뱀

https://www.acmicpc.net/problem/3190

3190번: 뱀

---

• 뱀이 움직일 때, 머리와 꼬리를 제외한 중간 몸통들의 위치를 계속 업데이트해 줄 필요가 없다.
• 맨 앞과 맨 뒤의 원소들만 추가, 제거하는 방식이기 때문에 덱을 사용해준다.
• 방향을 바꿔주는 타이밍에 대해서는, 매 초마다 큐의 top 과 비교하여 고려해준다.
• 현재 방향에서 오른쪽/왼쪽이 상대적이지만, dir 배열의 인덱스로 우-상-좌-하 의 순서를 갖는다면 현재 인덱스에서 오른쪽은 -1, 왼쪽은 +1 하여 다음 방향 인덱스를 가리킬 수 있다.
• 게임보드 N x N 배열을 통해 뱀의 몸통들을 관리함으로써 뱀의 머리가 몸에 닿았는지 쉽게 확인한다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, K, L;
int board[100][100];
int dir[4] = {0, -1, 0, 1};         // 뱀의 4방향

int main(void)
{
    cin >> N >> K;
    for(int i = 0, r, c ; i < K ; i++)
    {
        cin >> r >> c;
        board[r-1][c-1] = -1;
    }

    cin >> L;
    queue<pair<int,int>> q;
    for(int i = 0, X ; i < L ; i++)
    {
        char C;
        cin >> X >> C;
        q.push({X, (C == 'L' ? 1 : -1)});
    }

    deque<pair<int,int>> snake;
    board[0][0] = 1;
    snake.push_front({0,0});
    int cnt = 0;
    int curdir = 0;
    while(true)
    {
        int nextR = snake.front().first + dir[curdir];                  // 뱀머리의 다음 위치
        int nextC = snake.front().second + dir[3-curdir];
        if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) break;   // 벽에 부딪히면 종료
        
        if(board[nextR][nextC] == 0)                                    // 사과를 먹지 않을 경우
        {
            board[snake.back().first][snake.back().second] = 0;
            snake.pop_back();
        }
        else if(board[nextR][nextC] != -1) break;                       // 자기 몸에 부딪힌 경우
        
        snake.push_front({nextR, nextC});                               // 뱀 머리 움직임 처리
        board[nextR][nextC] = 1;

        cnt++;                                                          // 게임 시간 1초 증가
        if(q.size() && cnt == q.front().first)                          // 만약 뱀이 회전했다면
        {
            curdir = (curdir+4+q.front().second) % 4;                   // 뱀의 현재 방향 업데이트
            q.pop();
        }
    }
    cout << cnt+1 << endl;
}