[BOJ] 3190 뱀

 

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

3190번: 뱀

큰 알고리즘은 없고 그냥 구현 문제이다.

구현 문제를 풀 때 주의할 점은 놓치는 경우의 수가 없는지를 꼭 확인해야 한다는 것이다.

이 문제를 풀면서 뱀의 방향 정보를 모두 입력한 후에 끝나지 않는 경우를 파악하지 못하여 찾는데 상당한 시간을 사용했다.

만약 방향 정보를 모두 입력한 후에도 뱀이 죽지 않았다면 맵의 최대 길이를 실행시간으로 주었다.

#include <iostream>
#include <utility>
using namespace std;

int map[100][100]={0,};
pair<int,char> order[100];

int n,k,l,i,j;
int d;
char c;
bool d_left,d_right,d_up,d_down;

int d_size=1;

void find_last(int y,int x,int a){
    if(x<0||x>=n||y<0||y>=n) return;
    
    if(d_size==a){
        map[y][x]=0;
        return;
    }
    
    if(map[y][x]==2){ //오른쪽 방향에서 옴
        find_last(y,x-1,a+1);
    }else if(map[y][x]==3){ //왼쪽 방향에서 옴
        find_last(y,x+1,a+1);
    }else if(map[y][x]==4){ //위에서 옴
        find_last(y+1,x,a+1);
    }else if(map[y][x]==5){ //아래에서 옴
        find_last(y-1,x,a+1);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin>>n>>k;
    while(k--){
        cin>>i>>j;
        map[i-1][j-1]=1;
    }
    cin>>l;
    for(int i=0;i<l;i++){
        cin>>d>>c;
        order[i]=make_pair(d,c);
    }
    int ans=0;
    d_right=true;
    
    int now_command_time=0,command_time,befor_command_time,command_dir,index=0;
    int y=0,x=0;
    bool stop=false;
    
    map[0][0]=2;

    int before_command_time=0;
    while(1){
        //command가 끝날 경우 command_time을 map을 크기로 주어야 한다.
        if(index==l) command_time=100;
        else{
            before_command_time=now_command_time;
            now_command_time=order[index].first;
            command_time=now_command_time-before_command_time;
            command_dir=order[index++].second;
        }
        for(int i=0;i<command_time;i++){
            ans++;
            if(d_right){
                x++;
            }else if(d_left){
                x--;
            }else if(d_up){
                y--;
            }else if(d_down){
                y++;
            }
            
            //벽에 닿거나 자기 자신에 닿은 경우 stop
            if(x<0||x>=n||y<0||y>=n||(map[y][x]!=1&&map[y][x]!=0)){
                //cout<<"wall"<<'\n';
                stop=true;
                break;
            }
            
            if(map[y][x]==1) d_size++;
            
            if(d_right){
                map[y][x]=2;
            }else if(d_left){
                map[y][x]=3;
            }else if(d_up){
                map[y][x]=4;
            }else if(d_down){
                map[y][x]=5;
            }
            
            find_last(y,x,0);
            
        }
        
        if(stop) break;
        
        if(command_dir=='D'){
            if(d_right){
                d_right=false;
                d_down=true;
            }else if(d_left){
                d_left=false;
                d_up=true;
            }else if(d_up){
                d_up=false;
                d_right=true;
            }else if(d_down){
                d_down=false;
                d_left=true;
            }
        }else{
            if(d_right){
                d_right=false;
                d_up=true;
            }else if(d_left){
                d_left=false;
                d_down=true;
            }else if(d_up){
                d_up=false;
                d_left=true;
            }else if(d_down){
                d_down=false;
                d_right=true;
            }
        }
        
    }
    
   
    cout<<ans;
    return 0;
}