백준_뱀_3190

백준_뱀_3190

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

문제

• N*N 정사각 보드위에서 진행되고 몇몇 칸에는 사과가 놓여져 있다.
• 보드의 상하좌우 끝에 벽이 있다.
• 게임이 시작할때 뱀은 맨위 멘 좌측에 위치하고 뱀의 길이는 1이다.
• 뱀은 처음에 오른족을 향한다.
• 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따름
  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 고리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
    • 몸 길이는 변하지 않음
• 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나지는 계산하라.

어떻게 풀었는가

제한사항

• 보드의 크기 N이고, N은 2 이상 100 이하이다.
• 사과의 개수 K이고, K는 0 이상 100 이하이다.
  • 1행 1열에는 사과가 없다.
• 뱀의 방향 변환 횟수는 L이고, L은 1 이상 100 이하이다.
• 게임 시작 시각으로 X 초가 끝난 뒤 왼쪽 도는 오른쪽으로 방향을 회전시킨다.

풀이

• 끝나는 조건은 벽 또는 자신의 몸과 부딪히면 게임이 끝난다.
  • 벽은 보드의 크기를 이탈하면 충돌한다 생각하면 된다.
  • 자신의 몸과 부딪히는 경우는 1을 초과하는 순간부터 계산해야 한다.

1. 게임에 필요한 정보를 저장한다.

   • 보드 크기, 사과, 방향 변환에 대한 정보 저장

2. while 문을 사용하여 뱀을 이동시킨다.

   • 뱀이 이동하는 경우 벽과 충돌하는지 확인한다.
   • 뱀이 이동하는 경우 자신과 충돌하는지 확인한다.
   • 사과를 먹는지 확인한다. 사과를 먹는 경우 뱀의 길이를 증가시키고 해당 위치의 값을 false로 변경한다.
   • 방향 변환에 대한 정보를 확인한다.
     • 현재 시간 초가 방향 변환 시간과 같다면 방향을 전환한다.

3. 게임이 끝나는 시간을 출력한다.

코드

#include <iostream>
#include <deque>
#include <tuple>
using namespace std;

bool gameMap[101][101];

pair<int, int> moveDir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k, l;
    cin >> n >> k;
    // 사과
    for (int i = 0; i < k; ++i)
    {
        int x, y;
        cin >> x >> y;
        gameMap[x][y] = true;
    }

    cin >> l;
    deque<pair<int, char>> infoDirection(l);
    // 방향 전환
    for (int i = 0; i < l; ++i)
    {
        int num;
        char order;
        cin >> num >> order;

        infoDirection[i] = make_pair(num, order);
    }

    deque<pair<int, int>> infoMove;
    infoMove.push_back(make_pair(1, 1));
    int snakeLen = 1;
    int timeCount = 1;
    int idx = 0;

    while (true)
    {
        int posX = infoMove.back().first + moveDir[idx].first;
        int posY = infoMove.back().second + moveDir[idx].second;

        if (posX <= 0 || posX > n || posY <= 0 || posY > n)
        {
            break;
        }

        int len = infoMove.size();
        bool checkCrash = false;
        // 자신과 충돌하는지 확인
        for (int i = len - 1; i >= len - snakeLen; --i)
        {
            if (posX == infoMove[i].first && posY == infoMove[i].second)
            {
                checkCrash = true;
                break;
            }
        }
        if (checkCrash)
            break;
        if (gameMap[posX][posY])
        {
            ++snakeLen;
            gameMap[posX][posY] = false;
        }
        // 방향 전환
        if (!infoDirection.empty())
        {
            if (timeCount == infoDirection.front().first)
            {
                if (infoDirection.front().second == 'L')
                    idx = (idx + 3) % 4;
                else
                    idx = (idx + 1) % 4;
                infoDirection.pop_front();
            }
        }
        // 뱀이 지나온 위치 저장
        infoMove.push_back(make_pair(posX, posY));
        ++timeCount;
    }
    cout << timeCount << "\n";
    return 0;
}

결과