[백준/JAVA] BOJ 3190 - 뱀

시뮬레이션 한 번에 통과하고 살짝? 울 뻔 햇어요

👀 문제

3190번: 뱀 ✨ 골드 4

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

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

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

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

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

예제 입력

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력

9

🔑 키포인트

시뮬레이션 덱

✍️ 코드

📍 ArrayDeque 를 이용해 뱀의 경로 및 꼬리를 관리해 주는 방식으로 풀었고 사과는 2, 벽은 3으로 표시해서 구분해 주었다.

💡 풀면서 헷갈릴 것 같아서 주석도 열심히 달았어용...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ3190_뱀 {
    static class Dir {
        int sec;
        char direction;

        Dir(int sec, char direction) {
            this.sec = sec;
            this.direction = direction;
        }
    }

    static int n;
    static int[][] board;
    static boolean[][] visited;
    static ArrayList<Dir> change;
    static ArrayDeque<int[]> snake;
    static int dx = 0;
    static int dy = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        board = new int[n + 2][n + 2];
        visited = new boolean[n + 2][n + 2];
        snake = new ArrayDeque<>();

        // 벽 생성
        for (int i = 0; i < n + 2; i++) {
            for (int j = 0; j < n + 2; j++) {
                if (i == 0 || i == n + 1) {
                    board[i][j] = 3;
                } else if (j == 0 || j == n + 1) {
                    board[i][j] = 3;
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        change = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            board[x][y] = 2; // 사과
        }

        st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        for (int i = 0; i < l; i++) {
            st = new StringTokenizer(br.readLine());
            int sec = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
            change.add(new Dir(sec, dir));
        }
        snake.add(new int[] { 1, 1 });
        start(1, 1, 0);
    }

    static void start(int x, int y, int sec) {
        visited[x][y] = true;

        // 원래 방향대로 먼저 계산하고 회전
        if (change.size() > 0 && change.get(0).sec == sec) {
            char dir = change.get(0).direction;
            if (dir == 'D') { // 오른쪽으로 90도 회전
                if (dx == 0 && dy == 1) {
                    dx = 1;
                    dy = 0;
                } else if (dx == 1 && dy == 0) {
                    dx = 0;
                    dy = -1;
                } else if (dx == 0 && dy == -1) {
                    dx = -1;
                    dy = 0;
                } else if (dx == -1 && dy == 0) {
                    dx = 0;
                    dy = 1;
                }
            } else { // 왼쪽으로 90도 회전
                if (dx == 0 && dy == 1) {
                    dx = -1;
                    dy = 0;
                } else if (dx == -1 && dy == 0) {
                    dx = 0;
                    dy = -1;
                } else if (dx == 0 && dy == -1) {
                    dx = 1;
                    dy = 0;
                } else if (dx == 1 && dy == 0) {
                    dx = 0;
                    dy = 1;
                }
            }
            change.remove(0);
        }
        int nx = x + dx;
        int ny = y + dy;
        if (nx >= 0 && nx < n + 2 && ny >= 0 && ny < n + 2) {
            if (!visited[nx][ny]) {
                // 벽에 닿으면 끝
                if (board[nx][ny] == 3) {
                    System.out.println(sec + 1);
                    return;
                } else if (board[nx][ny] == 2) { // 사과면 먹기
                    board[nx][ny] = 0;
                    snake.addLast(new int[] { nx, ny }); // 머리
                    start(nx, ny, sec + 1);
                } else if (board[nx][ny] == 0) { // 사과 없으면
                    // 꼬리가 위치한 칸을 비워준다. (대신 길이는 변하지 않는다)
                    int[] tail = snake.pollFirst();
                    visited[tail[0]][tail[1]] = false;
                    snake.addLast(new int[] { nx, ny }); // 머리
                    start(nx, ny, sec + 1);
                }
            } else {
                // 자기 자신에 닿으면 끝
                System.out.println(sec + 1);
                return;
            }
        }
    }
}