뱀 3190

문제

접근 방법

큐 문제라는 생각이 강하게 들었다.
몸통은 머리가 간 길을 따라갈 뿐이라고 생각했다. 그렇기에 머리에서는 충돌, 방향 변경을 담당하고 몸통은 따라오며 마지막 꼬리 부분이 움직일지 말지를 결정해주면 될 것 같았다.

코드

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k, l, time = 0, dir = 0;
    int xPos[] = {1, 0, -1, 0}, yPos[] = {0, -1, 0, 1}; // 오른쪽 90도 +1 왼쪽 90도 -1
    bool appleBoard[101][101];
    bool bodyBoard[101][101];
    queue<pair<int, int>> snake;
    queue<pair<int, int>> dirTurn;
    cin >> n >> k;
    memset(appleBoard, false, sizeof(appleBoard));
    memset(bodyBoard, false, sizeof(bodyBoard));
    for (int i = 0; i < k; ++i)
    {
        int x, y;
        cin >> y >> x;
        appleBoard[x - 1][n - y] = true;
    }
    cin >> l;
    for (int i = 0; i < l; ++i)
    {
        int t;
        char d;
        cin >> t >> d;
        dirTurn.push({t, d == 'L' ? -1 : 1});
    }
    snake.push({0, n - 1}); // 맨위 맨좌측
    bodyBoard[0][n - 1] = true;
    while (true)
    {
        time++;
        int count = 0;
        pair<int, int> next;
        bool eatApple = false;

        while (count < snake.size())
        {
            if (count == 0) // 머리 사과, 몸통 충돌을 감지하고 앞서간다.
            {
                next = snake.front();
                snake.pop();
                pair<int, int> headPos = {next.first + xPos[dir],
                                          next.second + yPos[dir]};
                if (headPos.first < 0 || headPos.first >= n || headPos.second < 0 || headPos.second >= n || bodyBoard[headPos.first][headPos.second])
                {
                    cout << time;
                    return 0;
                }
                if (appleBoard[headPos.first][headPos.second])
                {
                    eatApple = true;
                    appleBoard[headPos.first][headPos.second] = false;
                }
                bodyBoard[headPos.first][headPos.second] = true;
                snake.push({headPos.first, headPos.second});
            }
            else // 몸통 : 앞부분을 따라간다.
            {
                pair<int, int> temp = snake.front();
                snake.pop();
                snake.push(next);
                next = temp;
            }
            ++count;
        }
        if (eatApple) // 꼬리 : 사과를 먹으면 몸통은 증가한다.
        {
            snake.push(next);
        }
        else // 아니면 꼬리 부분이 빠져줘야 한다.
        {
            bodyBoard[next.first][next.second] = false;
        }
        if (!dirTurn.empty() && dirTurn.front().first == time) // 방향 결정
        {
            dir += dirTurn.front().second + 4;
            dir %= 4;
            dirTurn.pop();
        }
    }
    return 0;
}

풀이

appleBoard에는 사과의 위치를 표시해준다.
dirTurn은 시간, 좌우 방향을 집어넣어 준다.
snake는 뱀의 머리, 몸통이 담겨있는 곳이다.
0, n - 1에서 시작되며 (방향에 대한 정보를 수정한다면 0, 0에서 시작할 수 있다.)
while(true) 안에서 시간에 따른 뱀의 이동이 시작된다.

eatApple을 통해 사과를 먹었는지 확인해준다.
if (count == 0)은 머리인지 확인해주는 조건문이다.
머리이면 이동을 하는데 이전 반복문에서 방향이 변경됐다면 변경된 방향으로 이동한다. 이동하며 사과, 몸의 충돌을 감지한다.

next는 앞에서 움직인 몸통이 뒤에 몸통에 전달하기 위해 남겨지는 값으로 뒤에 몸통은 next에 위치로 이동한다.

구글 계산기에서는 음수일지라도 나머지 연산을 하면 양수로 나왔다.
그래서 믿고 돌렸는데 틀렸다고 떴다.
왜 그럴까 싶으며 반례도 찾아보며 확인해본 결과 방향 전환에 음수가 들어가서 틀린 것이다.
다음부터는 이러한 사소한 문제를 조심해야겠다.