[3190번] 뱀

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

뱀 문제는 결국 구현이고 deque를 이용하여 머리와 꼬리 부분만 잘 해결해주면 된다.

이때 중요한건 입력부분에서 누적 시간으로 처리가 되고 있으니 문제를 잘 보고 prev, t를 이용하여야 하고

명령어가 끝이 났을 때 뱀이 벽에 박을때 까지 이동하도록 해주어야한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
 
#define UP 1
#define DOWN 2
#define LEFT  3
#define RIGHT 4
#define APPLE 2
#define SNAKE 1
#define LAND 0
 
using namespace std;
 
typedef pair<int, int> pii;
 
// 몸 1 사과 2
int arr[102][102];
int sy = 0, sx = 0;
int n, k, ans;
int dir = RIGHT;
deque<pii> dq;
 
void setSnake(){
    if (!(0 <= sy && sy < n) || !(0 <= sx && sx < n) || arr[sy][sx] == SNAKE)
    {
        printf("%d", ans);
        exit(0);
    }
 
    if (arr[sy][sx] == APPLE)
    {
        arr[sy][sx] = SNAKE;
        dq.push_front({ sy,sx });
    }
    else if (arr[sy][sx] == LAND)
    {
        arr[sy][sx] = SNAKE;
        dq.push_front({ sy,sx });
        arr[dq.back().first][dq.back().second] = LAND;
        dq.pop_back();
    }
}
int main()
{
    dq.push_back({ sy,sx });
    arr[sy][sx] = SNAKE;
 
    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; i++)
    {
        int y, x;
        scanf("%d %d", &y, &x);
 
        y--;
        x--;
        arr[y][x] = APPLE;
    }
 
    int m, prev = 0;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int t;
        char pos;
        scanf("%d %c", &t, &pos);
 
        int tmp = t;
        t -= prev;
    
        while (t--)
        {
            ans++;
            if (dir == UP) {
                sy --;
                setSnake();
            }
            else if (dir == DOWN) {
                sy ++;
                setSnake();
            }
            else if (dir == LEFT) {
                sx --;
                setSnake();
            }
            else if (dir == RIGHT) {
                sx ++;
                setSnake();
            }
        }
        
        prev = tmp;
 
        if (dir == UP && pos == 'L')
            dir = LEFT;
        else if (dir == UP && pos == 'D')
            dir = RIGHT;
        else if (dir == DOWN && pos == 'L')
            dir = RIGHT;
        else if (dir == DOWN && pos == 'D')
            dir = LEFT;
        else if (dir == LEFT && pos == 'L')
            dir = DOWN;
        else if (dir == LEFT && pos == 'D')
            dir = UP;
        else if (dir == RIGHT && pos == 'L')
            dir = UP;
        else if (dir == RIGHT && pos == 'D')
            dir = DOWN;
    }
 
    // 명령어가 없을때 마지막으로 뱀이 벽이 박을때 까지
    while (1)
    {
        ans++;
        if (dir == UP) {
            sy--;
            setSnake();
        }
        else if (dir == DOWN) {
            sy++;
            setSnake();
        }
        else if (dir == LEFT) {
            sx--;
            setSnake();
        }
        else if (dir == RIGHT) {
            sx++;
            setSnake();
        }
    }
 
    cout << ans << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>