(백준) 뱀 _ 3190

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

 

🐢 설명

2차원 맵을 뱀이 돌아다닌다. 이때 뱀이 자신의 몸에 닿거나 or 벽을 넘어가면 종료된다.

• 맵에 있는 사과를 먹으면 몸의 길이가 1 늘어난다.
• 그렇지 않으면 앞으로 계속 간다.
• 특정 초에 이동을 완료하고 방향만 바꾸는 명령이 주어진다.

사과를 안먹은 경우에는 이동 후 꼬리를 땡겨야 하는데 이를 위해서 뱀의 이동 내역을 담기 위한 Deque을 사용했다. 이동할 때 다음 위치의 유효성 검사를 하고 유효한 경우 사과 여부에 따라 구분하여 처리한다. 사과가 없다면 덱의 마지막을 뽑아서 제거하고, 있다면 다음 좌표를 덱의 앞에 넣어준다. 이동이 끝나면 명령의 시간과 현재 시간을 비교해서 같다면 왼쪽 / 오른쪽으로 방향만 바꿔준다.

 

조심할 점

• 초기 Deque에 처음 좌표 (0, 0)을 넣어줘야 한다.
• 사과가 놓이는 좌표는 (1, 1) 기준이므로 조정해줘야 한다.
• 13초에 이동하다가 벽을 넘거나 몸에 닿으면 게임은 13초에 끝난거다.
• 다음 좌표의 유효성이 체크되었다면 머리 좌표를 이동시켜야 한다.

🐢코드

package Gold이상문제_정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 뱀_3190 {
    static final int right = 0, up = 1, left = 2, down = 3;
    static int[] dy = {0, -1, 0, 1};
    static int[] dx = {1, 0, -1, 0};
    static final int A = 1;
    static final int BODY = 2;
    static int N;
    static int[][] map;
    static int appleCount;
    static int cmdCount;
    static int T = 0;
    static Snake snake;
    static Queue<CMD> cmds = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        appleCount = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < appleCount; i++) {
            String[] pos = br.readLine().split(" ");
            int y = Integer.parseInt(pos[0]) - 1;
            int x = Integer.parseInt(pos[1]) - 1;
            map[y][x] = A;
        }

        cmdCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < cmdCount; i++) {
            String[] cmd = br.readLine().split(" ");
            int time = Integer.parseInt(cmd[0]);
            String command = cmd[1];
            cmds.add(new CMD(time, command));
        }

        solve();
        System.out.println(T);
    }

    private static void solve() {
        LinkedList<Dot> body = new LinkedList<>();
        body.add(new Dot(0, 0));
        snake = new Snake(right, new Dot(0, 0), body);
        map[0][0] = BODY;

        while (true) {
            T++;
            if (!move()) return;
            // turn
            if (!cmds.isEmpty() && T == cmds.peek().time) {
                turn(cmds.poll().command);
            }
        }
    }

    private static void turn(String command) {
        if (command.equals("L")) {
            snake.dir = ++snake.dir % 4;
        } else {
            if (snake.dir == right) snake.dir = down;
            else snake.dir--;
        }
    }

    private static boolean move() {
        Dot now = snake.head;
        int dir = snake.dir;
        int ny = now.y + dy[dir];
        int nx = now.x + dx[dir];

        // 벽 || 몸통
        if (ny < 0 || nx < 0 || ny >= N || nx >= N) return false;
        if (map[ny][nx] == BODY) return false;

        // apple
        if (map[ny][nx] == A) {
            map[ny][nx] = BODY;
            snake.body.addFirst(new Dot(ny, nx));
        }// no apple
        else {
            map[ny][nx] = BODY;
            snake.body.addFirst(new Dot(ny, nx));
            if (snake.body.size() > 0) {
                Dot tail = snake.body.pollLast();
                map[tail.y][tail.x] = 0;
            }
        }
        snake.head.y = ny;
        snake.head.x = nx;
        return true;
    }

    private static class CMD {
        int time;
        String command;

        public CMD(int time, String command) {
            this.time = time;
            this.command = command;
        }
    }

    private static class Snake {
        int dir;
        Dot head;
        Deque<Dot> body;

        public Snake(int dir, Dot head, Deque<Dot> body) {
            this.dir = dir;
            this.head = head;
            this.body = body;
        }
    }

    private static class Dot {
        int y, x;

        public Dot(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

🐢 마무리