백준 3190번: 뱀

백준 3190번: 뱀

3190번: 뱀

요즘 알고리즘 푸는게 뜸해졌다. 게을러진거 같다. 다시 집중해서 공부해야 감을 잃지 않을 수 있다!

시뮬레이션 문제로 문제 이해를 하는데 조금 난해했다. 어렸을 때 뱀이 움직이면서 알맹이를 먹으면 점점 길어지는 게임을 해본적이 있을 것이다. 벽에 부딪히면 죽고, 길어진 자신의 몸에 부딪혀도 죽는다. 주어진 명령어로 최대한 오래 살아남으면 된다.

 

오른쪽, 왼쪽으로 90도씩 움직일 수 있으니 명령이 들어왔을 때 방향전환에 신중해야한다.

자신의 몸과 부딪혔을 때 게임 오버가 되어야하니 항상 이동했을 때의 자신의 몸의 좌표와 머리의 좌표를 확인해야한다.

사과를 먹었으면 사과는 없어져야한다! << 이것을 신경쓰지 못해 고생 좀 했다.

 

뱀이 움직이는 방법!

나는 덱(deque)을 사용해서 머리와 꼬리를 둘다 컨트롤 할 수 있게 했다. 뱀의 머리에서 뱀의 방향에서 한칸 전진한 칸에 사과가 없다면 덱의 front에 해당 칸을 추가하고 pop_back으로 꼬리를 잘랐다.

만약 사과를 먹는다면 front에 해당 칸을 추가하고 pop_back은 하지 않는다. 그리고 사과는 없애주자!

 

#include <iostream>
#include <cstring>
#include <deque>
#include <queue>
using namespace std;

struct snake
{
    int y;
    int x;
    int direction;
};

bool game_over = false;
int _sec = 0;
int board[102][102];
deque<snake> snk;
queue<pair<int, char>> mv;
int dirY[] = {0, 1, 0, -1}; //right, down, left, up
int dirX[] = {1, 0, -1, 0};
int n, k, l;

bool gameover(int headY, int headX)
{
    int len = snk.size();
    if (headY > n || headY <= 0 || headX > n || headX <= 0)
        return true;
    for (int i = 0; i < len; i++)
    {
        if (snk[i].y == headY && snk[i].x == headX)
        {
            return true;
        }
    }
    return false;
}

void play()
{
    while (!game_over)
    {
        
        int headY = snk.front().y;
        int headX = snk.front().x;
        int direction = snk.front().direction;
        //시간이 지나 명령이 들어왔을 때
        if (!mv.empty() && _sec == mv.front().first)
        {
            char comm = mv.front().second;
            //cout << comm << endl;
            mv.pop();
            //왼쪽으로 90도 회전
            if (comm == 'L')
            {
                direction = ((direction + 3) % 4);
            }
            //오른쪽으로 90도 회전
            else if (comm == 'D')
            {
                direction = ((direction + 1) % 4);
            }
        }
        headY += dirY[direction];
        headX += dirX[direction];
        //움직일 수 있는 곳인지 확인
        _sec += 1;
        //cout << _sec << "|" << headX << " " << headY << "|>" << direction << endl;
        game_over = gameover(headY, headX);

        //머리 이동
        snk.push_front({headY, headX, direction});
        if (board[headY][headX] == 1){
            board[headY][headX] = 0;
        }
        //사과를 먹은게 아니면 꼬리자르기
        else if (board[headY][headX] != 1)
        {
            snk.pop_back();
        }
    }
}

int main()
{

    //게임판 크기
    cin >> n;
    //init
    memset(board, 0, sizeof(board));

    //먹이가 있는 곳
    cin >> k;
    while (k--)
    {
        int y, x;
        cin >> y >> x;
        board[y][x] = 1;
    }

    //명령어
    cin >> l;
    while (l--)
    {
        int sec;
        char dir;
        cin >> sec >> dir;
        mv.push({sec, dir});
    }

    //뱀의 초기 위치
    snk.push_back({y : 1, x : 1, direction : 0});
    play();
    cout << _sec;
    return 0;
}