(C++) [백준 3190번] 뱀

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

3190번: 뱀

이걸 Dummy라고 부르는 지는 모르겠는데, 뱀을 이용해서 사과를 먹을 때 마다 길이가 길어지는 그런 류의 게임들을 얘기하는 것 같다. 비슷한 게임을 유튜브에서 찾아보니까 https://www.youtube.com/watch?v=kZr8sR9Gwag 이런 게임이 있다.

혹시나 처음 보시는 분들은 유튜브 영상을 보시면 좀 더 이해가 쉬울 것 같다.

 

뱀은 처음에 (1,1)에서 시작하며,오른쪽을 보고 있다. (* Zero-based numbering이 아니다) 뱀은 사과를 먹으면 길이가 1 증가하고, 뱀이 자기 자신의 몸통 혹은 벽에 부딪히는 순간 게임이 끝난다. 뱀은 1초에 1칸씩 이동할 수 있다고 할 때, 게임이 종료되는 시간을 구하면 된다.

뱀은 왼쪽 혹은 오른쪽으로 회전할 수 있는데 90도 시계방향 회전, 90도 반시계방향 회전이라고 생각하면 된다.

이때 이동을 먼저 한 후에 뱀을 회전시켜야 한다.

 

시뮬레이션 문제이기 때문에 문제의 의도에 맞게 충실히 구현하기만 하면 된다. 단, 뱀은 (1,1)에서 시작하기 때문에 배열의 크기를 딱 맞게 정하면 문제가 생길 수 있다. 

먼저 뱀을 움직이는 부분인데, 문제를 보면 다음과 같은 순서를 따른다.

1) 뱀의 머리를 늘려 다음칸에 위치시키고 2a) 사과가 있다면 사과를 먹고 길이를 1 증가, 2b) 사과가 없다면 꼬리가 위치한 칸을 줄여준다.

즉 먼저 1칸 늘려서 움직인 다음 사과가 있다면 유지, 없으면 꼬리를 1칸 줄이므로, 다음 칸에 뱀의 머리를 위치시킨 다음

사과가 있다면 유지하면 되고, 없으면 가장 마지막으로 들어온 원소를 없애면 되는것이다. 이까지 생각하면서 deque를 이용하면 좋겠다는 생각을 했다. 가장 처음(머리)에 있는 원소에 보고 있는 방향에 맞게 위치를 증감시킨 다음, 해당 위치에 사과가 없을 경우에만 가장 마지막(꼬리)에 있는 원소를 없애주면 되고, 이 과정이 끝나면 front에 증감시킨 값을 추가하면 된다.

 

다음으로 뱀을 회전하는 방법인데, 이건 별로 어렵지 않았다. 북쪽 방향을 0, 동쪽을 1, 남쪽을 2,서쪽을 3이라고 쳤을때

90도 시계방향 회전(오른쪽)은 현재 방향이 0일때는 1,1일때는 2,2일때는 3,3일때는 다시 0으로 해주면 되고,

반시계방향 회전은 현재 방향이 0일때는 3,3일때는 2,2일때는 1,1일때는 0으로 해주면 끝이기 때문이다.

 

1번 뱀을 움직이는 코드 move()는 다음과 같다.

 

int move()
{
    auto cur = dq.front();
    int x = cur.X;
    int y = cur.Y;
    if (dir == 0)
    {
        x += -1;
    }
    else if (dir == 1)
    {
        y += 1;
    }
    else if (dir == 2)
    {
        x += 1;
    }
    else
        y += -1;
    if (x < 1 || y < 1 || x > n || y > n) return 1;
    for (auto cur = dq.begin() + 1; cur != dq.end(); cur++)
    {
        if (x == cur->X && y == cur->Y) return 1;
    }
    if (board[x][y])
    {
        board[x][y] = 0;
    }
    else
        dq.pop_back();
    dq.push_front({x,y});
    return 0;
}

방향에 따라 x,y의 위치를 증감하고, 벽에 부딪힌 경우(20번째 줄), 머리가 몸통에 부딪힌 경우(21~24번째 줄)에는 1을 리턴하고, 정상 처리는 0을 리턴하도록 했다. 만약 1이 리턴된 경우에는 sec+1을 리턴하도록 했다.

회전하는 rotate()는 다음과 같다.

 
void rotate(int direction)
{
    if (direction == 0) // 왼쪽
    {
        if (dir == 0)
            dir = 3;
        else dir--;
    }
    else // 오른쪽
    {
        if (dir == 3)
            dir = 0;
        else dir++;
    }
}

딱히 설명할게 없다. 반시계 회전(왼쪽)은 0일때 3,아니면 1씩 빼주고, 시계 회전(오른쪽)은 3일때 0,아니면 1씩 더해주면 된다.

전체 코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#define MAX 103
#define X first
#define Y second
using namespace std;
int idx, dir, n, k, l, now, sec;
vector <pair<int, int>> v;
deque <pair<int, int>> dq;
int board[MAX][MAX];
int move()
{
    auto cur = dq.front();
    int x = cur.X;
    int y = cur.Y;
    if (dir == 0)
    {
        x += -1;
    }
    else if (dir == 1)
    {
        y += 1;
    }
    else if (dir == 2)
    {
        x += 1;
    }
    else
        y += -1;
    if (x < 1 || y < 1 || x > n || y > n) return 1;
    for (auto cur = dq.begin() + 1; cur != dq.end(); cur++)
    {
        if (x == cur->X && y == cur->Y) return 1;
    }
    if (board[x][y])
    {
        board[x][y] = 0;
    }
    else
        dq.pop_back();
    dq.push_front({x,y});
    return 0;
}
void input()
{
    int x, y;
    int r;
    char d;
    dq.push_front({ 1,1 });
    dir = 1;
    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> x >> y;
        board[x][y] = 1;
    }
    cin >> l;
    for (int i = 0; i < l; i++)
    {
        cin >> r >> d;
        if (d == 'L')
            v.push_back({ r,0 });
        else
            v.push_back({ r,1 });
    }
}
void rotate(int direction)
{
    if (direction == 0) // 왼쪽
    {
        if (dir == 0)
            dir = 3;
        else dir--;
    }
    else // 오른쪽
    {
        if (dir == 3)
            dir = 0;
        else dir++;
    }
}
int solve()
{
    while (true)
    {
        if (move() > 0) return sec + 1;
        else sec++;
        if (idx < v.size())
        {
            if (v[idx].X == sec)
            {
                rotate(v[idx++].Y);
            }
        }
    }
}
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    input();
    cout << solve();
}

solve()에서 계속해서 돌면서 move()의 결과값이 0 이상이면(1을 리턴했으면) sec+1을 리턴하고 종료하도록 했으며, 아닌 경우에는 1초를 증가한다.

v는 회전하는 몇초에 회전하는지, 어떤 방향으로 회전하는지 담겨있는 벡터이고, idx는 해당 v에 대한 인덱스이다.

idx는 내부 if문이 true일때마다 수행되므로 만약 idx가 v.size()보다 같거나 크다면 회전을 전부 완료한 상태이므로 더이상 수행되지 않게 한다.