[백준 3190]뱀

뱀

A. 접근법

본 문제는 시뮬레이션으로 문제 해석을 잘해서 코드로 옮기면 풀 수 있는 문제이다.

조건 중 별거 아닌 것 같지만 중요한 조건이 있었다. '먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다'이다. 처음에 구현 코드는 뒤의 꼬리부터 한 칸 씩 땡겼다. 이 경우, 1초뒤 머리를 다음칸에 위치시킬 때 그 곳에 꼬리가 있다면 게임이 종료되어야하는데 그렇지 못한다.

B. 구현

C. 코드

#include <iostream>
#include <vector>

using namespace std;
int T, N, K, L;
vector<vector<int>> table;
vector<vector<int>> snake;
vector<vector<int>> apple;
vector<vector<int>> moves;
int mvIdx;
int dir;
int nxt[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int solver(int time, int x, int y)
{
    if(L != 0 && mvIdx < L && time == moves[mvIdx][0]) {
        if(moves[mvIdx][1] == 0) {
            dir++;
        }
        else {
            dir--;
        }
        if(dir > 3)
            dir = 0;
        if(dir < 0)
            dir = 3;

        mvIdx++;
    }

    int nxtX = snake[0][0] + nxt[dir][0];
    int nxtY = snake[0][1] + nxt[dir][1];

    if(nxtX < 0 || nxtX >= N || nxtY < 0 || nxtY >= N)
        return time + 1;

    if(table[nxtX][nxtY] == 1) {
        vector<int> temp(2, 0);
        temp[0] = nxtX;
        temp[1] = nxtY;
        snake.insert(snake.begin(), temp);
        table[nxtX][nxtY] = 0;
    }
    else {
        for(int i = snake.size() - 1; i > 0; i--) {
            if(nxtX == snake[i][0] && nxtY == snake[i][1])
                return time + 1;

            snake[i][0] = snake[i - 1][0];
            snake[i][1] = snake[i - 1][1];
        }

        snake[0][0] = nxtX;
        snake[0][1] = nxtY;

    }

    return solver(time + 1, nxtX, nxtY);
}
int main() {
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d", &N);
        table.resize(N);
        table.clear();
        for(int i = 0; i < N; i++) {
            vector<int> tmp(N, 0);
            table.push_back(tmp);
        }

        scanf("%d", &K);
        apple.resize(K);
        apple.clear();
        int x, y;
        for(int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            table[x - 1][y - 1] = 1;
        }
        mvIdx = 0;
        scanf("%d", &L);
        char z;
        moves.resize(L);
        moves.clear();
        for(int i = 0; i < L; i++) {
            vector<int> tmp(2, 0);
            scanf("%d %c", &x, &z);
            tmp[0] = x;
            if(z == 'D') {
                tmp[1] = 0;
            }
            else if(z == 'L') {
                tmp[1] = 1;
            }
            else {}
            moves.push_back(tmp);
        }

        snake.resize(1);
        snake.clear();
        vector<int> tmp(2, 0);
        snake.push_back(tmp);

        dir = 0;

        printf("%d\n", solver(0, 0, 0));
    }
    return 0;
}

D. 결과