[백준 c++] 3190 뱀

문제

NxN 보드 위에서 뱀이 기어다니는 게임 🐍
뱀은 사과를 먹으면 길이가 늘어난다. 뱀은 1초마다 이동을 하고 벽(보드의 상하좌우 끝) 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
뱀의 초기 위치(x,y): (1,1)
뱀 초기 길이: 1

이동 규칙
1) 먼저 머리를 다음 칸에 위치시킴
2) 머리 칸에 사과 없으면 꼬리 줄어듦
3) 사과 있으면 사과 없어짐(몸길이 유지)

입력: N, K(사과 개수), 사과 위치, L(방향 전환 횟수), 방향 전환 정보
출력: 게임이 끝나는 초

풀이

크게 신경써야할 것은 꼬리와 회전

꼬리

꼬리 값은 늘 저장하고 있어야하므로, queue pair에 좌표를 저장했다.
1) 이동 전에 q.push({x,y})
2) 사과 안먹은 채 이동했으면 꼬리 줄이고, visited 해제
q.pop() visited[q.front().first][q.front().second] = 0

회전

뱀이 회전할 때 진행 방향을 바꿔줬다.
초기 이동은 x값은 유지된 채로 y값만 증가하는 형태다. 이때 오른쪽으로 회전하면 이동은 x값 증가, y값 유지된다.
이런식으로 (x,y)가중치 값을 pair로 저장한다.

pair<int,int> state[4] = [{0,1}, {1,0}, {0,-1}, {-1,0}]

현재 어떤 진행 방향을 따라야 하는지 저장해준다. 시작 직후엔 s = state[0]

오른쪽 회전하면 s++, 왼쪽 회전 s--
(단, s는 4번 주기로 돌아가므로 s = -1 =3 s = 4 = 0 )

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, k, l, a[101][101], apple[101][101], visited[101][101], s, y, x, cur;
queue<pair<int, char>> rot;
queue<pair<int, int>> tail;
pair<int, int> head, state[4];
int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int a1, a2;
        cin >> a1 >> a2;
        apple[a1][a2] = 1;
    }
    cin >> l;
    for (int i = 0; i < l; i++)
    {
        int sec;
        char d;
        cin >> sec >> d;
        rot.push({sec, d});
    }
    state[0] = {0, 1};
    state[1] = {1, 0};
    state[2] = {0, -1};
    state[3] = {-1, 0};
    y = 1, x = 1;
    while (1)
    {
        tail.push({x, y});
        y = y + state[s].second;
        x = x + state[s].first;
        if (y > n || x > n || y <= 0 || x <= 0 || visited[x][y])
            break;
        if (!apple[x][y])
        {
            auto t = tail.front();
            visited[t.first][t.second] = 0;
            tail.pop();
        }
        apple[x][y] = 0;
        visited[x][y] = 1;
        head.first = x, head.second = y;

        cur++;
        auto r = rot.front();
        if (cur == r.first)
        {
            if (r.second == 'D')
            {
                s += 1;
                if (s == 4)
                    s = 0;
            }
            else
            {
                s -= 1;
                if (s == -1)
                    s = 3;
            }
            rot.pop();
        }
    }
    cout << cur + 1 << "\n";
}