알고리즘50 :: BOJ_3190_뱀

뱀이 사과를 먹으면 몸의 길이가 늘어나고 그렇지 않으면 지나온 빈칸은 빈 칸이 되고 이동하게 되는 문제 입니다. 

 

뱀의 머리 ㅡ 몸통 ㅡ 꼬리 모두를 맵에 표시하는것 보다 머리의 이동 경로를 시간을 기준으로 맵에 표시해두는것이 핵심 입니다. 

 

즉, 뱀이 움직일때마다 current_time이 1씩 증가합니다. 맵에 표시됩니다.

 

사과를 먹으면 몸의 길이가 1 증가하게 됩니다. 

 

맵의 범위에서 빠져나가게 되거나 뱀의 머리가 몸에 닿는 경우인데 이 경우는 특수한 경우로 그림을 그려 생각해보면 쉽게 접근할 수 있습니다. 

 

	1	2	3	4	5
		9	8	7	6

가 있을 때 9인 위치에서

// 수정중

 

 

 

 

package backjun;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class backjun_3190_뱀 {
    static int n;
    static int apple_cnt;
    static int[][] map;
    static int[][] apple_map;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        apple_cnt = Integer.parseInt(br.readLine());
        apple_map = new int[n][n];
        map = new int[n][n];
        for(int i=0; i<apple_cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int apple_x = Integer.parseInt(st.nextToken())-1;
            int apple_y = Integer.parseInt(st.nextToken())-1;
            apple_map[apple_x][apple_y] = 1;
        }//사과 입력
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                map[i][j] = -1;
            }
        }//map init
        
        int current_time=0;
        int len = 1; //몸길이
        int init_x = 0;
        int init_y = 0;
        int dir = 0;
        String ndir="";
        int time = 0;
        map[init_x][init_y] = 0; //처음 뱀이 위치한 곳
        int direction_cnt = Integer.parseInt(br.readLine()); //direction 
        for(int i=0; i<=direction_cnt; i++) {
            time = 98765421; //time init
            ndir = "L"; //ndir init
            if(i<direction_cnt) { //벽에 닿지도 않고 몸에 닿지도 않은 경우 
                StringTokenizer st= new StringTokenizer(br.readLine());
                time = Integer.parseInt(st.nextToken());
                ndir = st.nextToken();
            }
            while(current_time<time) { //입력으로 주어진 N시간 안에 뱀이 움직일 수 있다면 
                current_time +=1; //시간 증가하고
                init_x += dx[dir]; //x이동
                init_y += dy[dir]; //y이동
                
                if(init_x<0 || init_x>=n || init_y<0 || init_y>=n) {
                    //벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
                    System.out.println(current_time);
                    return ; 
                }
                if(apple_map[init_x][init_y]==1) {
                    len+=1;
                    apple_map[init_x][init_y] = 0;
                }//사과를 먹은 경우
                
                if(map[init_x][init_y]!=-1 && current_time-map[init_x][init_y]<=len) {
                    System.out.println(current_time);
                    return ; 
                }//뱀의 머리가 몸에 닿았을때 
                
                map[init_x][init_y] = current_time;
                
                }
                if(ndir.equals("D")){
                    //오른쪽
                    dir = (dir+1)%4;
                }else {
                    //왼쪽 
                    dir = (dir+3)%4;
                } //방향
        }
    }
}