BOJ 3190 - 뱀

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

 

구현

이 문제에서 크게 구현할 부분은 사과를 먹었을 때 꼬리를 늘리는 작업, 뱀 몸통에 부딪혔을 때 게임이 종료되게 하는 기능 이다.

뱀의 위치를 효율적으로 나타내기 위한 자료구조를 생각해내는 것이 핵심이다. 뱀이 한 번 움직이면 꼬리와 머리가 한 칸씩 움직이기 때문에 앞과 뒤를 다룰 수 있는 deque를 이용하면 된다.

 

문제에서 헤맸던 부분이 방향을 돌리는 시점이다.

예를 들어 10초에 왼쪽으로 움직인다는 뜻은 이전 방향으로 10까지 움직인 후에 방향을 바꾼다는 뜻이다!

 

구현 문제 중 쉬운 편에 속한다.

 

코드

#include <iostream>
#include <deque>
#include <queue>

using namespace std;

#define UP_DIR 0
#define RIGHT_DIR 1
#define DOWN_DIR 2
#define LEFT_DIR 3

int N; // NxN
int K; // 사과 개수
int L; // 움직임 횟수
int map[101][101];
deque<pair<int, int>> snake_pos;
vector<pair<int, char>> rotate_seq;
int snake_dir;
int curr_time;
int curr_x;
int curr_y;
/*
위 0 , 오 1, 아래 2, 왼 3
*/

void init() {
    snake_pos.push_back(make_pair(0, 0));
    cin >> N;
    cin >> K;
    while (K--) {
        int x, y;
        cin >> x >> y;
        map[x-1][y-1] = 2;
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        int t; char r;
        cin >> t >> r;
        rotate_seq.push_back(make_pair(t, r));
    }

    snake_dir = RIGHT_DIR;

    map[0][0] = 1;
}

void rotate(char rotate_dir) {
    if (rotate_dir == 'L') { // 왼쪽
        snake_dir--;
        if (snake_dir < 0) {
            snake_dir = 3;
        }
    }
    else {
        snake_dir = (snake_dir + 1) % 4;
    }
}

bool isApple() {
    return map[curr_x][curr_y] == 2;
}

bool isBlocked() {
    if (map[curr_x][curr_y] == 1)
        return true;
    else if (curr_x < 0 || curr_x > N-1 || curr_y < 0 || curr_y > N-1)
        return true;
    return false;
}

bool move(int move_time) {
    while (curr_time < move_time) {
        if (snake_dir == UP_DIR) {
            curr_x--;
        }
        else if (snake_dir == RIGHT_DIR) {
            curr_y++;
        }
        else if (snake_dir == DOWN_DIR) {
            curr_x++;
        }
        else {
            curr_y--;
        }

        if (isBlocked()) {
            curr_time++;
            return true;
        }
        
        if (!isApple()) {
            pair<int, int> back_pos = snake_pos.back();
            map[back_pos.first][back_pos.second] = 0;
            snake_pos.pop_back();
        }
        

        snake_pos.push_front(make_pair(curr_x, curr_y));
        map[curr_x][curr_y] = 1;
        

        curr_time++;
    }
    return false;
}

int main() {
    bool gameOver = false;
    init();
    for (int i = 0; i < L; i++) {
        int t = rotate_seq[i].first;
        char r = rotate_seq[i].second;
        
        gameOver = move(t);
        if (gameOver) {
            break;
        }
        else {
            rotate(r);
        }
    }

    if (!gameOver) {
        move(10001);
    }
    
    cout << curr_time;

    return 0;
}