[백준][C++] 3190 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

 

 

알고리즘 종류

구현

 

 

 

사고 과정

뱀의 몸을 저장하기 위해서 deque으로 배열을 만들어 줍니다.

 

뱀의 움직임을 저장할 배열 rotate를 만들어 줍니다.

 

1. 뱀이 움직일 시간이면 방향을 바꿔줍니다.

 

2. 머리를 움직여 봅니다. 그리고 아래 조건으로 확인합니다.

    2-1. 끝? 범위 밖 또는 자신의 몸과 부딪혔는지 확인합니다.

    2-2. 사과? 사과가 있으면, 몸을 늘려줍니다. 사과가 없으면 꼬리 부분을 비웁니다.

 

 

 

구현(C++)

#include <iostream>
#include <deque>
 
using namespace std;
 
 
int n, k, l;
 
int mat[101][101];
char rotate[10001];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};                                                     
 
 
bool isValid(int y, int x){
    return (y>=1 && y<=n) && (x>=1 && x<=n);
}
 
 
void solution(){
    
    deque<pair<int, int> > dq;
    dq.push_back({1,1});
    mat[1][1] = 2;
    int d = 1;
    
    int t = 0;
    while(true){
        
        // change direction
        if(rotate[t] == 'D'){
            if(d==0) d=3;
            else if(d==3) d=2;
            else if(d==2) d=1;
            else if(d==1) d=0;
        }
        else if(rotate[t] == 'L'){
            if(d==0) d=1;
            else if(d==1) d=2;
            else if(d==2) d=3;
            else if(d==3) d=0;
        }
        
        int ny = dq.front().first + dir[d][0];
        int nx = dq.front().second + dir[d][1];
        
        // end
        if(!isValid(ny, nx) || mat[ny][nx] == 2) {
            cout << t + 1 << endl;
            return;
        }
        
        // apple?
        if(mat[ny][nx] == 3){
            dq.push_front({ny, nx});
            mat[ny][nx] = 2;
        }
        else{
            dq.push_front({ny, nx});
            mat[ny][nx] = 2;
            mat[dq.back().first][dq.back().second] = 0;
            dq.pop_back();
        }
        
        t++;
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    cin >> k;
    
    int y, x;
    for(int i=0; i<k; i++){
        cin >> y >> x;
        mat[y][x] = 3;
    }
    
    cin >> l;
    
    int s;
    char c;
    for(int i=0; i<l; i++){
        cin >> s >> c;
        rotate[s] = c;
    }
    
    solution();
}

 

 

시행착오