3190 뱀

3190. 뱀 / c++ / Gold4 / 1시간 10분

문제

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

1. 보드의 크기 N, 사과의 갯수 K, 뱀의 방향 변환 횟수 L
2. 뱀은 아래와 같은 움직임을 갖는다.
   1. 뱀의 길이가 1 늘어서 머리가 다음칸으로 움직임
   2. 만약 다음칸이 사과라면 꼬리가 줄지 않음
   3. 만약 다음칸이 사과가 아니라면 꼬리가 1칸 줄음
3. 뱀의 머리가 자기 자신이나 벽에 닿으면 게임 오버
4. 방향 전환은 숫자 X와 문자 C로 이루어 진다.
   1. 게임 시작 후 X초가 지났을 때 방향 전환이 이루어진다.
   2. C가 ‘D’이면 현재 방향에서 오른쪽으로 90도 회전
   3. C가 ‘L’이면 현재 방향에서 왼쪽으로 90도 회전
5. 위와 같을 때 게임이 끝나는 시간을 출력하시오.

접근 방식

자료구조, 큐

1. 뱀 게임은 해본적이 있어서 대략적인 작동 원리는 이해했다.
2. 우선 뱀의 머리가 늘어나고, 다음으로 뱀의 꼬리가 줄어든다는 점에 주목했다.
3. 계속해서 새로운 머리가 들어오고, 제일 처음 들어온 머리(꼬리)가 사라진 다는 점에서 FIFO인 Queue를 사용하기로 했다.
4. 보드는 vector로 N만큼 초기화 하고, 0은 빈칸, 1은 뱀, 2는 사과를 나타내기로 했다.
5. 이동 방향은 map으로 쉽게 찾을 수 있게 했고, 방향 전환은 switch문으로 현재 방향에 따라 다르게 변환되도록 했다.
6. 만약 뱀의 다음 이동 칸이 보드의 끝이거나 자기 자신일 경우 현재까지의 게임 시간을 출력

문제 풀이

#pragma GCC optimzie("Ofast")
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int N, K, L, nowOrder = 0, answer = 0;
char moveDir = 'R';
map<char, int> deltaY = { {'R', 0}, {'L', 0}, {'U', -1}, {'D',1} };
map<char, int> deltaX = { {'R', 1}, {'L', -1}, {'U', 0}, {'D', 0} };
vector<vector<int>> board;
queue<pair<int, int>> snake;
vector<pair<int, char>> moveOrder;

void SwitchDir(char nextDir)
{
    switch (moveDir)
    {
    case 'U':
        if (nextDir == 'D') moveDir = 'R';
        else moveDir = 'L';
        break;
    case 'D':
        if (nextDir == 'D') moveDir = 'L';
        else moveDir = 'R';
        break;
    case 'L':
        if (nextDir == 'D') moveDir = 'U';
        else moveDir = 'D';
        break;
    case 'R':
        if (nextDir == 'D') moveDir = 'D';
        else moveDir = 'U';
        break;
    }
}

bool Move()
{
    answer++;
    pair<int, int> now = snake.back();
    int nextY = now.first + deltaY[moveDir];
    int nextX = now.second + deltaX[moveDir];
    if (nextY < 0 || nextY >= N) { cout << answer << '\n'; return false; }
    else if (nextX < 0 || nextX >= N) { cout << answer << '\n'; return false; }
    else if (board[nextY][nextX] == 1) { cout << answer << '\n'; return false; }
    else
    {
        snake.push({ nextY, nextX });
        if (board[nextY][nextX] != 2)
        {
            pair<int, int> tail = snake.front();
            board[tail.first][tail.second] = 0;
            snake.pop();
        }
        board[nextY][nextX] = 1;
    }

    if (nowOrder < moveOrder.size())
    {
        if (answer == moveOrder[nowOrder].first) SwitchDir(moveOrder[nowOrder++].second);
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;
    board = vector<vector<int>>(N, vector<int>(N, 0));

    int x, y;
    for (int i = 0; i < K; ++i)
    {
        cin >> y >> x;
        board[y - 1][x - 1] = 2;
    }
    board[0][0] = 1;
    snake.push({ 0,0 });

    cin >> L;

    //Print();
    char nextDir;
    int moveTime;
    for (int i = 0; i < L; ++i)
    {
        cin >> moveTime >> nextDir;
        moveOrder.push_back({ moveTime, nextDir });
    }
    while (true)
    {
        if (!Move()) return 0;
    }

    return 0;
}

다시 생각해 볼 점

1. 방향 전환에서의 X가 현재 게임 진행 시간인 줄 모르고, 매번 X만큼 진행 후 C로 변환했더니 오류가 났었다. 아무리 해결하려고 해도 안됐었는데 역시나 문제의 조건을 잘못 이해하고 있는 것이었다.
2. 지금이 방향 전환을 할 시간인지 체크하는 부분에서 nowOrder가 이미 moveOrder의 범위를 벗어났음에도 계속 체크하려고 해서 오류가 났었다. 문제 로직을 명확하게 파악하고 진행하지 않아서 생긴 부분이었다. if문으로 처리해서 수정하였다.
3. 4방향을 다 순회할 필요가 있을 때는, 그냥 배열로 dY, dx 를 체크했었지만, 이처럼 특정 방향을 찾아야할 때는 map을 이용하니 깔끔하게 처리되었다.
4. 빡구현 문제라 생각보다 시간을 많이 잡아먹었다. 위와 같은 실수를 안하려면 문제를 제대로 이해하고 로직을 짜야하겠다.