백준 3190 : 뱀

제로베이스 강의에 연습문제로 있길래 그냥 하드코딩으로 풀었는데 백준에 있는 문제였다..

시간이 좀 걸렸지만 게임만드는 것 같아서 재밌게 풀었던 것 같다.

그리고 확실히 세세하게 필요한 기능을 나눠서 구현한 후 순서에 맞게 조립하니까 잘 풀어진 것 같다.

 

문제 설명

---

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.

- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

- 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        ArrayList<ArrayList<Integer>> apples = new ArrayList<>();
        HashMap<Integer, String> moves = new HashMap<>();
        for (int i = 0; i < K; i++) {
            ArrayList<Integer> apple = new ArrayList<>();
            apple.add(sc.nextInt());
            apple.add(sc.nextInt());
            apples.add(apple);
        }
        int L = sc.nextInt();
        sc.nextLine();

        for (int i = 0; i < L; i++) {
            String[] s = sc.nextLine().split(" ");
            moves.put(Integer.parseInt(s[0])+1,s[1]);
        }

        solution(N,K,L,apples,moves);
    }

    public static void solution(int N, int K, int L, ArrayList<ArrayList<Integer>> apples, HashMap<Integer,String> moves) {
        // N x N 보드판 작성, 테두리칸도 작성
        int[][] board = new int[N + 2][N + 2];

        // 보드판에 사과 놓기
        for (ArrayList<Integer> apple : apples) {
            int y = apple.get(0);
            int x = apple.get(1);
            board[y][x] = 1;
        }

        // 보드판 테두리 작성
        for (int i = 0; i < N + 2; i++) {
            board[0][i] = 2;
            board[i][0] = 2;
            board[N + 1][i] = 2;
            board[i][N + 1] = 2;
        }

        // 방향 제어
        ArrayDeque<String> directions = new ArrayDeque<>();
        directions.addLast("r");
        directions.addLast("d");
        directions.addLast("l");
        directions.addLast("u");

        String curDirection = directions.peekFirst();


        // 보드판 규칙 0은 비어있는 공간, 1은 사과 2는 뱀
        // 벽이나 자기 자신에 닿으면 죽는다.

        int time = 0; // 초 세기

        // 처음 위치에 뱀 위치시키기
        board[1][1] = 2;

        // 뱀 몸통
        ArrayDeque<Integer[]> snake = new ArrayDeque<>();

        // 머리 좌표
        int xH = 1;
        int yH = 1;

        snake.addFirst(new Integer[]{yH, xH});

        // 게임 시작
        while (true) {
            time++;
            // 방향 바꾸기
            // 무브맵을 통해서 방향바꿀 시간이 되었는지 체크
            if (moves.containsKey(time)) {
                // 방향 명령 꺼내기
                String direction = moves.get(time);
                // 방향 분기
                if (direction.equals("D")) {
                    directions.addLast(directions.pollFirst());
                    curDirection = directions.peekFirst();
                } else if (direction.equals("L")) {
                    directions.addFirst(directions.pollLast());
                    curDirection = directions.peekFirst();
                }
            }

            // 방향별 이동
            if (curDirection.equals("r")) {
                xH++;
            } else if (curDirection.equals("d")) {
                yH++;
            } else if (curDirection.equals("l")) {
                xH--;
            } else if (curDirection.equals("u")) {
                yH--;
            }

            // 사과 있는지 체크 , 사과 없으면 꼬리 부분 보드판 0으로 바꾸기
            if (board[yH][xH] == 0) {
                Integer[] tail = snake.pollFirst();
                board[tail[0]][tail[1]] = 0;
            }

            // 정지 조건
            if(board[yH][xH]==2){
                System.out.println(time);
                break;
            }

            snake.addLast(new Integer[]{yH, xH});
            board[yH][xH] = 2;
        }
    }
}