[BOJ] 3190번 | 뱀 (C++)

🔗문제 보러가기

3190번: 뱀

 

🧑🏻‍💻풀이 과정

문제 로직 자체는 어렵지 않은데, 구현할 게 많아서 상당히 귀찮았던 문제입니다. 문제를 보면, 다음과 같은 문장을 읽을 수 있습니다.

 

뱀의 머리가 먼저 한 칸 이동합니다.
그 위치에 사과가 없다면, 꼬리도 한 칸 이동하고, 사과가 있다면 꼬리는 이동하지 않습니다.

 

위 문장을 구현하려면, 뱀의 꼬리가 이동할 방향에 대한 정보가 필요합니다. 뱀의 꼬리가 이동해야 할 방향은 이전까지 뱀의 머리가 이동했던 방향들이므로, 뱀의 머리가 이동했던 경로들이 차례대로 필요합니다. 즉, Queue를 사용하면 됩니다.

 

 

하지만, 또 하나 중요하게 봐야 할 조건이 있습니다.

 

게임 시작 시간으로부터 X초가 지난 후, 왼쪽 또는 오른쪽으로 뱀이 90도 방향을 틀 수 있습니다.

 

이것은 초기 기본 이동 방향을 기준으로 하여, 배열 인덱스로 관리할 수 있습니다. 처음 초기 이동 방향은 오른쪽입니다.

방향 정보만을 관리하면 되기 때문에, (행, 열)로 표시하자면 다음과 같습니다.

위     : (-1, 0)
아래   : (1, 0)
왼쪽   : (0, -1)
오른쪽 : (0, 1)

 

기본 시작이 오른쪽 방향이므로, 오른쪽 방향에서 90도로 틀 수 있는 방향은 위쪽과 아래쪽입니다.

그렇다면, 다음과 같이 방향 정보 배열을 구성할 수 있습니다.

// [0]상, [1]우, [2]하, [3]좌
vector<Direction> _directions { {-1, 0}, { 0, 1 }, { 1, 0 }, { 0, -1 } };
int directionIdx = 1;  // 초기 기본 이동 방향은 오른쪽이므로 1번 인덱스

 

이 상태에서 만약 왼쪽으로 회전해야 한다면 현재 인덱스에 -1을, 오른쪽으로 회전해야 한다면 +1을 해주면 됩니다.

물론 현재 인덱스가 0인데 왼쪽으로 가야하는 경우에는 배열의 맨 마지막 원소로 바꿔주고, 현재 인덱스가 배열 크기를 넘지 않기 위해 % 처리해주는 예외 처리는 별도로 해줘야 겠지요.

 

 

🛠️알고리즘

여기까지 했다면, 문제를 풀기 위한 핵심 코어는 완성한 셈입니다. 이제 다음과 같이 알고리즘을 적용하여 시뮬레이션 해주면 됩니다.

맵에서 칸을 구별해주기 위해, 저는 다음과 같이 선언하였습니다.

const int EMPTY = 0;
const int SNAKE = 1;
const int APPLE = 2;

Position _head = Position(0, 0);       // 머리 위치
Position _tail = Position(0, 0);       // 꼬리 위치

1. 현재 게임 시간에서 방향을 바꿔야 하는지 검사합니다.
   • 바꿔야 한다면, 인덱스를 변경해줍니다.
2. 게임 진행 시간을 1초 증가시킵니다.
3. 뱀의 머리를 이동 방향으로 한 칸 이동시킵니다.
   • 이 때, 이 이동 방향을 별도의 Queue에 저장하여, 나중에 꼬리가 움직일 때 하나씩 뽑아 사용하도록 합니다.
4. 만약 뱀의 머리가 이동한 위치가 자기 자신의 몸이거나 벽이면 종료합니다.
5. 아니라면, 머리가 이동한 위치에 사과가 있는지 확인합니다.
   • 사과가 없다면, 현재 꼬리 위치는 EMPTY로 채우고, Queue에서 하나 뽑아 해당 방향으로 꼬리를 한 칸 이동합니다.
   • 사과가 있다면, 몸의 길이가 늘어나므로 아무런 처리를 하지 않아도 됩니다.
6. 뱀이 이동한 머리 위치 칸을 SNAKE로 저장합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Direction = pair<int, int>;

class Board
{
public:
    Board();

    void StartGame();
    int ShowPlayTime() { return _playTime; }
private:
    void CheckTurning();
    void CheckApple();

private:
    struct TurningData
    {
        TurningData() { }
        TurningData(int time, char directionMark) : _time(time), _directionMark(directionMark) { }
        int     _time;
        char    _directionMark;
    };

    struct Position
    {
        Position() { }
        Position(int row, int col) : _row(row), _col(col) { }
        Position operator+(const Direction& other) { return Position(_row + other.first, _col + other.second); }

        int _row;
        int _col;
    };

private:
    vector<vector<int>> _board;
    queue<TurningData>  _turningData;
    queue<Direction>    _tailMoveDirections;

    // (-1, 0):상, (0, 1):우, (1, 0):하, (0, -1):좌
    vector<Direction> _directions { {-1, 0}, { 0, 1 }, { 1, 0 }, { 0, -1 } };
private:
    int _directionIdx = 1;
    int _playTime = 0;
    int _N;

    Position _head = Position(0, 0);       // 머리 위치
    Position _tail = Position(0, 0);       // 꼬리 위치
private:
    const int EMPTY = 0;
    const int SNAKE = 1;
    const int APPLE = 2;
};

Board::Board()
{
    int N, appleCount, turningInformations;
    cin >> N >> appleCount;

    _N = N;

    // 1. N x N 보드판 만들기
    _board.resize(N);
    for (int i = 0; i < N; i++)
        _board[i].resize(N);

    _board[0][0] = SNAKE;  // 뱀 처음 위치 등록

    // 2. 맵에 사과 채우기
    for (int i = 0; i < appleCount; i++)
    {
        int row, col;
        cin >> row >> col;
        _board[row - 1][col - 1] = APPLE;
    }

    // 3. 방향 전환 포인트 저장하기
    cin >> turningInformations;
    for (int i = 0; i < turningInformations; i++)
    {
        int time;
        char mark;
        cin >> time >> mark;
        _turningData.emplace(TurningData(time, mark));
    }
}

void Board::CheckTurning()
{
    if (!_turningData.empty())
    {
        TurningData data = _turningData.front();

        if (data._time == _playTime)
        {
            _turningData.pop();
            int addIdx = (data._directionMark == 'L') ? -1 : 1;

            if (_directionIdx == 0 and addIdx == -1)
            {
                _directionIdx = _directions.size() - 1;
                return;
            }

            _directionIdx = (_directionIdx + addIdx) % _directions.size();
        }
    }
}

void Board::CheckApple()
{
    if (_tailMoveDirections.empty())
        return;

    // 사과가 없다면, 꼬리 이동
    if (_board[_head._row][_head._col] != APPLE)
    {
        Direction next = _tailMoveDirections.front();
        _tailMoveDirections.pop();

        _board[_tail._row][_tail._col] = EMPTY;
        _tail = _tail + next;
    }
}

void Board::StartGame()
{
    while (true)
    {
        // 1. 방향을 바꿔야 하는지 확인
        CheckTurning();
        _playTime++;

        _head = _head + _directions[_directionIdx];
        _tailMoveDirections.emplace(_directions[_directionIdx]);

        // 2. 벽에 부딪혔다면 게임 종료
        if (_head._row < 0 or _head._row >= _N or _head._col < 0 or _head._col >= _N)
            break;

        // 3. 머리가 자기 몸과 부딪히면 게임 종료
        if (_board[_head._row][_head._col] == SNAKE)
            break;

        // 4. 사과 여부 확인
        CheckApple();

        _board[_head._row][_head._col] = SNAKE;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);

    Board gameBoard;
    gameBoard.StartGame();
    cout << gameBoard.ShowPlayTime();
    return 0;
}