BOJ 3190 ) 뱀 (C++)

3190번: 뱀

 큐에 뱀의 몸 좌표를 넣어주고 이동마다 머리와 꼬리를 관리해준다. 처음에 접근을 잘못해서 매 이동마다 큐 내부의 모든 몸의 좌표를 이동시켜주려고 하다가 포기했었는데 생각해보니 머리와 꼬리만 관리해줘도 상관없겠다는 결론에 이르렀다. 

 dir이라는 변수를 두고 왼쪽 회전인 경우 -1, 오른쪽으로 회전인 경우 +1을 해줌으로써 방향 관리를 해주고 cnt와 routeidx로 해당 회차에 방향 이동이 일어나는지를 관리해줬다. 매 이동에서 다음 좌표에 과일이 있으면 좌표를 큐에 넣어줌으로써 뱀의 길이를 증가시키고, 과일이 없는 경우 머리 좌표를 넣고 꼬리 좌표를 하나 삭제해준다. 

 

#include <iostream>
#include <queue>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int dx[4]={0,1,0,-1};   // 오른쪽. 아래, 왼쪽, 위
int dy[4]={1,0,-1,0};
int N, K, r, c, L, X,C;
deque<pii> q;
int arr[102][102];
pair<int, char> route[101];
int t=0;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>N>>K;
    for(int i=0;i<K;i++){
        cin>>r>>c;
        arr[r][c]=1; // 과일 위치
    }

    q.push_back({1,1});
    arr[1][1]=-1;
    cin>>L;
    for(int i=0;i<L;i++){
        cin>>route[i].x>>route[i].y;
    }
    int cnt =0, dir=0, routeidx=0;
    bool fin = false;
    
    while(1){
        int curx = q.front().x;
        int cury = q.front().y;
       // cout<<curx<<' '<<cury<<' '<<route[routeidx].x<<' '<<cnt<<'\n';
        if(route[routeidx].x==cnt){
            if(route[routeidx].y=='L'){
                dir = (dir+3)%4;
            } else {
                dir = (dir+1)%4;
            }
            routeidx++;
        }
        int nx = curx+dx[dir];
        int ny = cury+dy[dir];
        if(nx<=0||ny<=0||nx>N||ny>N) break;
        if(arr[nx][ny]<0) break;
        if(arr[nx][ny]>0) {
            arr[nx][ny]=-1;
            q.push_front({nx,ny});
        } else {
            arr[nx][ny]=-1;
            q.push_front({nx, ny});
            int tempx = q.back().x;
            int tempy = q.back().y;
            q.pop_back();
            arr[tempx][tempy]=0;
        }
        cnt++;
    }

    cout<<cnt+1;
    return 0;
}