백준 3190 / 뱀

뱀 게임. 

예전에 전자사전으로 많이 했던 게임인데, 그 때 그 게임과는 조금 다르다.

이 게임은 대가리가 먼저나가고 꼬리가 그 다음으로 잘리는 방식이다.

즉, ㄷ자로 모양으로 있는 4칸짜리 뱀이 있다고 가정할때,

밑으로 이동하면 전자사전의 게임 경우 죽지 않는데, 

이 게임은 대가리가 먼저 나가 꼬리에 부딪혀 죽는다.

그리고....

문제를 똑바로 읽어야한다. 나 같은 경우는

맨위 왼쪽이 (1,1)이라고 문제에 떡하니 적혀있는데, 

(0,0)인줄알고 사과의 값을 그대로 받았더니 원래 있어야 할 사과의 위치보다 행+1, 열+1에 위치시켜 헤멨었다.

제발 문제 좀 제대로 읽자!

뱀의 대가리를 중심으로 큐를 사용했고

뱀은 deque를 사용했다. (사과를 먹는 경우 대가리만 늘고 꼬리가 줄지 않아, push_front를 사용해야되기 떄문)

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int map[101][101];
 
vector<int>sec;
vector<char>dir;
deque<pair<int, int>>snake;
 
 
int main() {
    //freopen("Text.txt", "r", stdin);
    
    int n;
    int apcnt,dircnt;
 
    cin >> n;
    cin >> apcnt;
    for (int i = 0; i < apcnt; i++) {
        int ax, ay;
        cin >> ax >> ay;
        map[ax-1][ay-1] = 1;
    }
    
    cin >> dircnt;
 
 
    for (int i = 0; i < dircnt; i++) {
        int sectmp;
        char dirtmp;
        cin >> sectmp >> dirtmp;
 
        sec.push_back(sectmp);
        dir.push_back(dirtmp);
    }
 
    queue<pair<int, int>>q;
    q.push({ 0, 0 });
    snake.push_back({ 0,0 });
 
    bool start = true;
 
    int len = 0;
    int ans = 0;
 
 
    int nowdir = 0;
    
    //0 오른쪽, 1 아래, 2 왼쪽, 3 위
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        ans++;
 
        if (start == true) {
            start = false;
            if (map[0][1] == 1) {
                len++;
                map[0][1] = 0;
                snake.push_front({ 0,1 });
                q.push({ 0,1 });
            }
            else {
                snake.push_front({ 0,1 });
                snake.pop_back();
                q.push({ 0,1 });
            }
        }
 
        else {
            int nx, ny;
            if (nowdir == 0) {
                nx = x;
                ny = y + 1;
            }
            if (nowdir == 1) {
                nx = x + 1;
                ny = y;
            }
            if (nowdir == 2) {
                nx = x;
                ny = y - 1;
            }
            if (nowdir == 3) {
                nx = x - 1;
                ny = y;
            }
 
            if (nx >= 0 && nx < n && ny >= 0 && ny < n ) {
                if (map[nx][ny] == 0) {
                    for (int i = 0; i < snake.size(); i++) {
                        if (nx == snake[i].first && ny == snake[i].second) {
                            cout << ans << endl;
                            return 0;                        
                        }
                    }
                    snake.push_front({ nx,ny });
                    snake.pop_back();
                    q.push({ nx,ny });
                }
                if (map[nx][ny] == 1) {
                    map[nx][ny] = 0;
                    snake.push_front({ nx, ny });
                    q.push({ nx,ny });
                }
            }
            else {
                cout << ans << endl;
                return 0;
            }
 
            for (int i = 0; i < sec.size(); i++) {
                if (ans == sec[i]) {
                
                    if (dir[i] == 'D') {
                        nowdir++;
                        if (nowdir == 4) {
                            nowdir = 0;
                        }
                    }
                    if (dir[i] == 'L') {
                        
                        nowdir--;
                        if (nowdir == -1) {
                            nowdir = 3;
                        }
                    }
                    break;
                }
            }
        }
    }
}