[BOJ-3190]뱀

http://acmicpc.net/problem/3190

[풀이방법]

DEQUEUE 를 이용해서 풀 수 있다. 

방문위치를 갱신하며,

이동하는 위치에 사과가 있다면 앞자리에 사과 위치를 push_front 한다.

사과가 없다면 push_front 로 사과위치를 하고, pop_back 을 한다.

그리고 게임이 종료할 때까지 이과정을 진행하면 된다.

[C++11]

#include<cstdio>
#include<vector>
#include<deque>
#define din1(a) scanf("%d", &a)
using namespace std;
int N, K, L;
const int m = 111;
 
const int dr[] = { 0,1,0,-1 }; // R D L U
const int dc[] = { 1,0,-1,0 };
int im[m][m];
int c_d = 0;
 
struct pos {
    int r, c;
    pos() {}
    pos(int ir, int ic) : r(ir), c(ic) {}
};
 
deque<pos> snake;
 
void init() {
    for (int i = 0; i < N+2; i++) { //[0,N+1]
        im[i][0] = im[0][i] = 1;
        im[i][N+1] = im[N+1][i] = 1;
    } // wall
}
int main() {
    
    din1(N);
    im[1][1] = 1;
    init();
    snake.push_front(pos(1, 1));
    din1(K); // apple
    for (int i = 0; i < K; i++) {
        int r, c;
        scanf("%d%d", &r, &c);
        im[r][c] = -1; // apple
    }    
    din1(L); // dir 
    int c_time = 0; // current time
    bool is_end = false;
    for (int i = 0; i < L; i++) {
        int time;
        char id;
        scanf("%d %c", &time, &id);
        while ( c_time < time ) {
            int tr = snake[0].r + dr[c_d];
            int tc = snake[0].c + dc[c_d];
            bool is_eat = false;
            if (im[tr][tc] == -1) {
                is_eat = true;
                snake.push_front(pos(tr, tc));
                im[tr][tc] = 1;
            }
            else if(im[tr][tc] == 1){
                is_end = true;                
            }
 
            if (!is_eat && !is_end) {
                snake.push_front(pos(tr, tc));
                im[tr][tc] = 1;
                int tail = snake.size() - 1;
                im[snake[tail].r][snake[tail].c] = 0;
                snake.pop_back();
            }
            c_time++;
            if (is_end) break;
        }
        if (is_end) break;
        if (c_time == time) {
            if (id == 'D') c_d = (c_d + 1) % 4;// right
            else if (id == 'L') c_d = (c_d - 1 < 0) ? 3 : c_d - 1;
        }
    }
 
    if(is_end) printf("%d\n", c_time);
    else if (!is_end) {
        while (1) {
            int tr = snake[0].r + dr[c_d];
            int tc = snake[0].c + dc[c_d];
            bool is_eat = false;
            if (im[tr][tc] == -1) {
                is_eat = true;
                snake.push_front(pos(tr, tc));
                im[tr][tc] = 1;
            }
            else if (im[tr][tc] == 1) {
                is_end = true;
            }
 
            if (!is_eat && !is_end) {
                snake.push_front(pos(tr, tc));
                im[tr][tc] = 1;
                int tail = snake.size() - 1;
                im[snake[tail].r][snake[tail].c] = 0;
                snake.pop_back();
            }
            c_time++;
            if (is_end) break;
        }
        printf("%d\n", c_time);
    }
    
 
    return 0;
}