[C++] 백준 3190번: 뱀!

문제

난이도 : 골드 4
백준 3190번 : 뱀!

코드

#include <bits/stdc++.h>

using namespace std;

int N, K, L;
int arr[104][104];

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

struct Snake
{
    vector<pair<int, int>> pos;
    int dv = 1;

    pair<int, int> head;
    pair<int, int> tail;

    bool Move()
    {
        bool apple = false;

        head = pos[0];
        tail = pos[(int)pos.size() - 1];

        // 머리의 이동
        pair<int, int> prev = pos[0];
        pos[0].first = head.first + dy[dv];
        pos[0].second = head.second + dx[dv];

        // 예외 처리 -> 벽 밖으로 나가거나 몸통에 부딪히거나
        if (pos[0].first < 0 || pos[0].second < 0 || pos[0].first >= N || pos[0].second >= N) return false;
        if (arr[pos[0].first][pos[0].second] == 2) return false;

        // 사과를 먹었으면
        if (arr[pos[0].first][pos[0].second] == 1)
            apple = true;

        // 머리를 제외한 몸통의 이동
        for (int i = 1; i < pos.size(); i++)
        {
            pair<int, int> temp = pos[i];
            pos[i] = prev;
            prev = temp;
        }

        if (apple)
        {
            Eat();
        }
        else
        {
            arr[tail.first][tail.second] = 0;
        }

        Mark();

        return true;
    }

    void Rotate(char C)
    {
        if (C == 'L')
        {
            if (dv == 0)
                dv = 3;
            else
                dv--;
        }
        else if (C == 'D')
        {
            if (dv == 3)
                dv = 0;
            else
                dv++;
        }
    }

    void Eat()
    {
        pos.push_back(tail);
    }

    void Mark()
    {
        for (int i = 0; i < pos.size(); i++)
        {
            arr[pos[i].first][pos[i].second] = 2;
        }
    }
};

int main()
{
    cin >> N;
    cin >> K;

    Snake s;
    s.pos.push_back({ 0, 0 });

    arr[0][0] = 2;

    for (int  i = 0; i < K; i++)
    {
        int y, x;
        cin >> y >> x;
        arr[y - 1][x - 1] = 1;
    }

    cin >> L;
    vector<pair<int, char>> v;

    for (int i = 0; i < L; i++)
    {
        int X; char C;
        cin >> X >> C;
        v.push_back({ X,C });
    }

    int rotate_cnt = 0;
    int answer = 0;

    for (int t = 1; ; t++)
    {
        if (!s.Move())
        {
            answer = t;
            break;
        }

        if (rotate_cnt < L && t == v[rotate_cnt].first)
        {
            s.Rotate(v[rotate_cnt].second);
            rotate_cnt++;
        }
    }

    cout << answer;

    return 0;
}

풀이

겨우 겨우 구현했는데 사실은 엄청 쉬운 풀이가 있어서 매우 허무했던 문제,, 그래도 풀었으니까 한잔해
뱀의 움직임을 구현하기 위해 Snake라는 구조체를 만들었다. arr 배열을 만들어 1은 사과, 2는 뱀의 몸통을 나타내게 했다.

---

먼저 Snake 구조체를 보자. 뱀의 한 칸마다의 몸통의 위치를 저장하기 위해 pair<int, int>형 벡터 pos를 멤버변수로 둔다.
dv는 뱀이 가리키고 있는 방향을 나타냄, 전역 변수로 선언한 dy와 dx의 인덱스로 이해하면 됨.
그리고 뱀의 머리와 꼬리를 가리키는 head와 tail 변수도 만들었다(굳이 필요하진 않다고 생각)
Move 함수를 보자
현재 뱀이 있는 위치의 head와 tail을 업데이트하고 뱀의 머리부터 방향벡터를 이용해 이동한다. 벽 밖으로 나가거나 몸통에 부딪히면 바로 false를 리턴해 게임 종료
사과를 먹었으면 apple 변수를 true로 만들어 나중에 처리할 것임
머리를 제외한 몸통의 이동은 prev 변수로 한 칸 앞에 있는 위치로 이동하게 만들었다.
그리고 apple의 값에 따라 먹었으면 pos 벡터에 tail위치를 push 해준다. (몸통이 한 칸씩 이동했으므로 원래 tail 자리는 빈 칸임) 먹지 않았으면 그대로 tail을 0으로 바꿔줌
그런 다음 맵에 Mark() 함수로 뱀의 위치를 찍어준다

---

입력 받은 시간이 지나면 회전하는 것은 rotate_cnt로 현재까지 회전한 횟수를 지정하고 시간이 지나면 머리의 이동 방향을 바꿔준다. Rotate 함수로 가면 회전 방향에 따라 dv의 값을 바꾸는 것을 볼 수 있다. 머릿속으로 상상해보면 이해감

---

이렇게 이동을 구현해주면 끝난다
사실 Deque 자료구조를 이용하면 엄청 쉽게 풀리는 문제임,,,

결과