[C++] 백준 3190번: 뱀

🔗 문제

3190번: 뱀

3190번: 뱀

 

🖍 풀이

종료 조건을 보면 map의 범위를 벗어나거나 뱀 자기 자신과 부딪히면 게임이 종료된다.

 

뱀의 길이가 변하면서 이동하는 건 간단하게 deque로 해결했다.

머리를 내밀 때 push_front(), 꼬리가 짧아지면 pop_back()으로 해결했다.

 

더불어 map에 EMPTY, APPLE, SNAKE 세 종류의 데이터를 저장해서 뱀의 유무를 판단해주었다.

 

 

너무 친절하게도 시간 오름차순으로 방향 전환이 되어서 queue에 넣고 방향 전환시간이 되면 pop해줬다.

현재 방향 d에 따른 오른쪽, 왼쪽 방향 전환은 내 마음대로 동서남북을 숫자로 표현해서 간단하게 해결했다.

if(turn.front().second == 'L')
		d = (--d < 0 ? 3 : d);
else if(turn.front().second == 'D')
		d = (++d > 3 ? 0 : d);

 

💾  소스

#include <iostream>
#include <queue>

const int MAX  = 100 + 1;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

std::queue<std::pair<int, char>> turn;

enum TYPE
{
    EMPTY = 0,
    SNAKE = 1,
    APPLE = 7
};

int N, K, L;
int map[MAX][MAX] = {EMPTY, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    return true;
}

void show()
{
    std::cout << "===show===" << std::endl;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
            std::cout << map[i][j] << ' ';
        std::cout << '\\n';
    }
}

int dummy()
{
    int answer = 0, d = 0;
    std::deque<std::pair<int, int>> snake;
    
    snake.push_front({0, 0});
    map[0][0] = SNAKE;
    
    while(1)
    {
        //show();
        int x = snake.front().first;
        int y = snake.front().second;
        
        if(!turn.empty() && turn.front().first == answer)
        {
            if(turn.front().second == 'L')
                d = (--d < 0 ? 3 : d);
            else if(turn.front().second == 'D')
                d = (++d > 3 ? 0 : d);
            turn.pop();
        }

        int nextX = x + dx[d];
        int nextY = y + dy[d];
        
        if(!isValid(nextX, nextY) || map[nextX][nextY] == SNAKE)
            break;
        
        if(map[nextX][nextY] == EMPTY)
        {
            //짧아져야해
            map[snake.back().first][snake.back().second] = EMPTY;
            snake.pop_back();
        }
        x = nextX; y = nextY;
        snake.push_front({x, y});
        map[x][y] = SNAKE;
        ++answer;
    }
    
    return answer+1;
}

int main()
{
    int x, y;
    char c;
    
    std::cin >> N >> K;
    for(int i=0; i<K; ++i)
    {
        std::cin >> x >> y;
        map[x-1][y-1] = APPLE;
    }

    std::cin >> L;
    for(int i=0; i<L; ++i)
    {
        std::cin >> x >> c;
        turn.push({x, c});
    }
    
    std::cout << dummy();
    
    return 0;
}