백준 3190 뱀 - 큐, 시뮬레이션

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

 

난이도 골드4

 

문제

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

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

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

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

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

 

 

문제 풀이를 위한 기능 

<방향>

- turnRight : 현재 방향에 따라 오른쪽에 맞는 방향으로 세팅한다.

- turnLeft : 현재 방향에 따라 왼쪽에 맞는 방향으로 세팅한다.

 

<뱀>

- goStraight : 현재 방향에 맞게 한칸 전진하고, 전진한 칸을 몸통으로 등록한다. 

- getTailY : 등록되어있는 몸통의 가장 끝(FIFO 구조에서 pop) 의 y 좌표를 반환한다. 

- getTailX : 등록되어있는 몸통의 가장 끝(FIFO 구조에서 pop) 의 x 좌표를 반환한다. 

- removeTail : 등록되어있는 몸통의 가장 끝(FIFO 구조) 을 제거한다.

 

 

이러한 기능들로, 시간에 맞춰 방향을 바꾸어 주고, 사과가 있다면 그냥 지나가고,

사과가 없는 칸이었다면 removeTail을 사용하여 꼬리를 하나 지우고, 해당하는 칸도 비워주도록 구현합니다.

 

구현한 코드에서 아쉬운 부분은,  아직 제가 java 에 미숙해서 class 를 멋대로 썼다는 점입니다. 

특히 java 에서는 Pair를 담는 queue 구현을 직접해야하는 걸 알고 충격이었습니다. 이번에는 그냥 Y,X 를 붙여서 따로 구현했는데 다음엔 구현해보려고 합니다. ㅎㅎ

 

 

import java.util.*;
import java.io.*;


public class Main {
    private static final int R = 1;
    private static final int L = 2;
    private static final int U = 3;
    private  static final int D = 4;

    public static class Direction{

        private static int direction;

        public Direction(){

            direction = R;
        }
        private static void setUp(){
            direction = U;
        }

        private static void setDown(){
            direction = D;
        }

        private static void setLeft(){
            direction = L;
        }

        private static void setRight(){
            direction = R;
        }
        public static void turnRight(){
            //up
            if (direction == U) {
                direction = R;
            }
            //right
            else if(direction == R){
                direction = D;
            }

            //down
            else if(direction == D){
                direction = L;
            }

            //left
            else if(direction == L){
                direction = U;
            }
        }

        public static void turnLeft(){
            //up
            if (direction == U) {
                direction = L;
            }
            //left
            else if(direction == L){
                direction = D;
            }

            //down
            else if(direction == D){
                direction = R;
            }

            //right
            else if(direction == R){
                direction = U;
            }
        }

        public static int getDirection(){
            return direction;
        }

    }
    public static class Snake{
        private static Direction direction = new Direction();
        private static Queue<Integer> tailY = new LinkedList<>();
        private static Queue<Integer> tailX = new LinkedList<>();;
        private static int y;
        private static int x;
        public Snake(){
            y = 0;
            x = 0;
            tailY.add(y);
            tailX.add(x);
        }

        public static void setLocation(int y, int x){
            y = y;
            x = x;
        }

        public static void goStraight(){
            if (direction.getDirection() == U) {
                y--;
            } else if (direction.getDirection() == D) {
                y++;
            } else if (direction.getDirection() == L) {
                x--;
            } else if (direction.getDirection() == R) {
                x++;
            }
            tailY.add(y);
            tailX.add(x);
        }

        public static int getY(){
            return y;
        }

        public static int getX(){
            return x;
        }

        public static void turnLeft(){
            direction.turnLeft();
        }

        public static void turnRight(){
            direction.turnRight();
        }

        public void removeTail(){
            tailY.poll();
            tailX.poll();
        }

        public int getTailY(){
            return tailY.peek();
        }
        public int getTailX(){
            return tailX.peek();
        }

        @Override
        public String toString(){
            return "snake in " + y + " " + x + " direction : " + direction.getDirection();
        }

    }


    private static int[][] board = new int[101][101];
    private static int[] snakeRotations = new int[10001];
    private static int N;
    private static final int APPLE = 100;
    private static final int SNAKE = 99;
    public static void main(String[] args) throws IOException {
        BufferedReader bf  = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());

        int appleCount = Integer.parseInt(bf.readLine());
        for(int i = 0; i < appleCount; i++){
           String[] loc = bf.readLine().split(" ");
           int appleY = Integer.parseInt(loc[0]);
           int appleX = Integer.parseInt(loc[1]);
            board[appleY-1][appleX-1] = APPLE;
        }

        int snakeRotateCount = Integer.parseInt(bf.readLine());
        for (int i = 0; i < snakeRotateCount; i++) {
            String[] loc = bf.readLine().split(" ");
            int time = Integer.parseInt(loc[0]);
            char direction = loc[1].charAt(0);
            snakeRotations[time] = direction;
        }

        int t = 0;
        Snake snake = new Snake();
        for(t = 1; t < N * N; t++){


            snake.goStraight();
            int y = snake.getY();
            int x = snake.getX();

//            System.out.println("at t " + t + snake);
            if(x < 0 || x >= N || y < 0 || y >= N){
                break;
            }

            if (board[y][x] == SNAKE){
                break;
            }
            else if(board[y][x] != APPLE){
                int removeY = snake.getTailY();
                int removeX = snake.getTailX();
                board[removeY][removeX] = 0;
                snake.removeTail();
            }
            else{
                board[y][x] = 0;
            }

            board[y][x] = SNAKE;

            if (snakeRotations[t] == 0) {
                ;
            } else if (snakeRotations[t] == 'D') {
                snake.turnRight();
            } else if (snakeRotations[t] == 'L') {
                snake.turnLeft();
            }

        }

        System.out.println(t);
    }
}