[Java] 백준 3190번 : 뱀

1. 문제

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

3190번: 뱀

 

 

2. 풀이과정

1. map이라는 2차원 배열에 1은 사과, 2는 뱀으로 표시한다. 또 다른 2차원 배열에는 다음 꼬리를 찾는 데 사용할 방향을 표시한다.

2. 머리는 해당 방향으로 한 칸 전진한다.

3. 사과를 먹으면, 그냥 넘어가고 사과를 먹지 않으면, 꼬리를 제거한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, map[][], dir[][], d, sx, sy, ex, ey, time, len;
    static int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1};

    public static boolean move(int sec){
        while(time+1 <= sec){
            time++;
            dir[sx][sy] = d;
            sx += dx[d];
            sy += dy[d];

            if(0>sx || sx>=N || 0>sy || sy>=N || map[sx][sy]==2){
                return false;
            }

            if(map[sx][sy]==1){
                len++;
            }
            else{
                map[ex][ey] = 0;
                if(len==1){
                    ex = sx;
                    ey = sy;
                }
                else{
                    map[ex][ey] = 0;
                    int temp = dir[ex][ey];
                    ex += dx[temp];
                    ey += dy[temp];
                }
            }
            map[sx][sy] = 2;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dir = new int[N][N];
        int K = Integer.parseInt(br.readLine());
        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1] = 1;
        }

        int L = Integer.parseInt(br.readLine());
        int sec[] = new int[L];
        char direction[] = new char[L];
        for(int i=0; i<L; i++){
            st = new StringTokenizer(br.readLine());
            sec[i] = Integer.parseInt(st.nextToken());
            direction[i] = st.nextToken().charAt(0);
        }

        //simulation
        sx = sy = ex = ey = 0;
        map[sx][sy] = 2;
        d = 2;
        len = 1;
        boolean result = true;
        for(int i=0; i<L; i++){
            result = move(sec[i]);
            if(!result){
                break;
            }
            if(direction[i]=='L'){
                d = (d-1+3)%4+1;
            }
            else{
                d = d%4+1;
            }
        }
        if(result){
            move(time+N);
        }
        System.out.println(time);
    }
}

 

결과