[BOJ 3190] 뱀(C++)

뱀 (Gold5)

문제

전체 문제 보기

3190번: 뱀

접근법

이번 문제는 Snake game 이라는 유명한 고전 게임의 일부를 구현하는 문제입니다. 문제에서 제시한 기능들을 하나씩 구현하여 문제를 해결할 수 있습니다.

뱀의 이동과 사과

가장 중요한 뱀을 구현하기 위해서는 큐를 사용할 수 있습니다. 뱀이 이동 메커니즘은 다음과 같습니다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

큐에 머리 위치를 push하고 이동할 때마다 pop 한다면 큐에는 항상 꼬리의 위치가 있음이 보장됩니다. 이를 활용하여 다음과 같이 구현할 수 있습니다.

• 먼저 뱀의 머리를 이동 후 머리 위치를 큐에 push한다.
• 이동한 칸에 사과가 있다면 이동을 종료한다.
• 이동한 칸에 사과가 없다면, 큐의 첫 번째 원소를 칸을 비우고 큐를 pop 한다.

뱀의 회전

그리고 뱀의 회전에는 다음과 같이 방향 배열을 만든 다음, 회전 방향에 따라서 인덱스를 증가시켜 뱀의 다음 이동방향을 결정할 수 있습니다.

// 좌표를 추상화 한 Pos 구조체
struct Pos {
    int r{};
    int c{};
};
// 4가지 방향. 회전시 인덱스를 변경하여 방향을 결정할 수 있다.
const array<Pos, 4> dirs{ Pos(0,1),Pos(-1,0),Pos(0,-1),Pos(1,0) };

게임 지형

게임이 진행되는 지형인 레벨 같은 경우 각 칸마다 4가지 상태를 가질 수 있도록 다음과 같이 선언하여 사용할 수 있습니다.

//E: 비어있는 상태
//A: 사과가 있는 상태
//S: 뱀이 있는 상태
//W: 벽이 있는 상태
using Level = vector<vector<char>>;

이렇게 선언된 레벨을 디버깅을 위해 출력해보면 다음과 같습니다. (첫 번째 테스트 케이스에서 time 6인 상태입니다.)

time: 6
WWWWWWWW
W      W
W    A W
W   S  W
W   S  W
W  A   W
W      W
WWWWWWWW

전체 구현

위의 기능들을 바탕으로 아래와 같이 구현할 수 있습니다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <array>
using namespace std;
int const INF = 101;

//' ': 비어있는 상태
//'A': 사과가 있는 상태
//'S': 뱀이 있는 상태
//'W': 벽이 있는 상태
using Level = vector<vector<char>>;

void PrintLevel(const Level& level)
{
    for (auto& row : level)
    {
        for (auto ch : row)
        {
           printf("%c", ch);
        }
        printf("\n");
    }

    printf("\n");
}
struct Pos {
    Pos() {}
    Pos(int _r, int _c) : r(_r), c(_c) {}
    int r{};
    int c{};
    Pos& operator+=(const Pos& rhs)
    {
        r += rhs.r;
        c += rhs.c;
        return *this;
    }
};

class Snake {
public:
    Snake(Level& _level);
    bool Move(int to, int& endTime);
    void Rotate(char ch);
private:
    Level& level;
    int dirIndex{};
    const array<Pos, 4> dirs;
    Pos curDir;
    Pos head;
    int time;
    queue<Pos> body;
};
Snake::Snake(Level& _level) 
    : level(_level)
    , dirIndex(0)
    , dirs{ Pos(0,1),Pos(-1,0),Pos(0,-1),Pos(1,0) }
    , curDir(dirs[dirIndex])
    , head(1,1)
    , time(0)
{
    level[1][1] = 'S';
    body.push(Pos(1, 1));
}
bool Snake::Move(int to, int& endTime)
{
    while (time < to)
    {
        time++;
        //머리 이동
        head += curDir;
        Pos tail = body.front();

        switch (level[head.r][head.c])
        {
            // 빈칸일 경우 머리 push, 꼬리 pop
        case ' ':
            body.push(head);
            level[head.r][head.c] = 'S';
            level[tail.r][tail.c] = ' ';
            body.pop();
            break;

            // 사과가 있는 경우 사과 먹고 머리만 push, pop 안함
        case 'A':
            body.push(head);
            level[head.r][head.c] = 'S';
            break;

            // 몸을 만나거나 벽을 만난 경우 현재 시간 저장후 false 반환
        case 'S':
        case 'W':
            endTime = time;
            return false;
            break;
        }
        //printf("time: %d\n", time);
        //PrintLevel(level);
    }
    return true;
}
void Snake::Rotate(char ch)
{
    if (ch == 'L')
    {
        dirIndex = (dirIndex + 1) % 4;
    }
    else if (ch == 'D')
    {
        dirIndex = (dirIndex + 3) % 4;
    }
    curDir = dirs[dirIndex];
}
int main() {

    // N 크기의 Level 생성 
    int N; //(2 ≤ N ≤ 100) 
    scanf("%d ", &N);
    Level level(N + 2);
    for (int i = 0; i < N + 2; ++i)
    {
        level[i].resize(N + 2, 'W');
    }

    for (int i = 1; i < N + 1; ++i)
    {
        for (int j = 1; j < N + 1; ++j)
            level[i][j] = ' ';
    }

    // 사과 위치 입력 받음
    int K; // (0 ≤ K ≤ 100)
    scanf("%d ", &K);

    while (K--)
    {
        int r, c;
        scanf("%d %d ", &r, &c);
        level[r][c] = 'A';
    }

    // Snake 생성
    Snake snake(level);
    int L; // (1 ≤ L ≤ 100)
    scanf("%d ", &L);

    // 회전 입력 받기
    int endTime{};
    while (L--)
    {
        int X;
        char R;
        scanf("%d %c ", &X, &R);
        if (snake.Move(X, endTime) == false)
        {
            // 충돌 발생시 시간 출력후 프로그램 종료
            printf("%d\n", endTime);
            return 0;
        }
        snake.Rotate(R);
    }

    // 명령이 끝나도 충돌하지 않았다면 끝까지 직진
    snake.Move(INF, endTime);
    printf("%d\n", endTime);
    return 0;
}