[백준] 3190 뱀 - Java

문제

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

 

---

 

문제 개요

'Dummy'라는 도스게임에서는 뱀이 정사각형 NxN 보드에서 사과를 먹으며 움직이다가 벽이나 자신의 몸에 부딪히면 게임이 끝납니다. 뱀은 처음에 길이가 1이며 매 초마다 이동합니다. 이동 중 사과를 먹으면 길이가 늘어나고, 사과가 없으면 꼬리를 줄입니다. 게임은 뱀이 벽이나 자신의 몸과 부딪힐 때 종료되며, 주어진 사과의 위치와 방향 변환 정보에 따라 게임이 몇 초에 끝나는지를 구하는 문제입니다.

접근 방법

1. 시뮬레이션을 통한 구현
   이 문제는 단순한 규칙에 따라 뱀의 움직임을 시뮬레이션하면 해결할 수 있습니다. 뱀의 이동을 매 초마다 시뮬레이션하면서 벽이나 자기 몸과 충돌하는지 체크합니다. 사과가 있는 경우, 사과를 먹고 몸을 늘리며, 없는 경우에는 꼬리를 줄이는 방식으로 처리합니다.
2. 방향 전환 처리
   뱀은 주어진 시간에 맞춰 방향을 전환합니다. 이를 위해 미리 방향 전환 정보를 큐에 저장하고, 시뮬레이션 중 해당 시간이 되면 방향을 변경하는 방식으로 구현합니다.

해결 과정

1. 맵 초기화 및 사과 배치
   입력받은 보드 크기와 사과의 위치에 따라 맵을 설정합니다. 맵에는 사과는 'A', 뱀의 몸은 'S'로 표시하여 관리합니다.
2. 뱀의 이동 시뮬레이션
   시뮬레이션은 뱀이 매초 이동하면서 벽이나 자기 자신의 몸에 부딪히면 종료됩니다. 방향 전환 정보는 큐에 저장하고, 해당 시간이 되면 뱀의 이동 방향을 변경합니다.
   • 이동 시 사과가 있으면 뱀의 몸이 늘어나며, 사과를 먹은 칸을 'S'로 업데이트합니다.
   • 사과가 없으면 꼬리를 줄이면서 몸을 이동합니다.
   • 뱀의 머리가 벽 또는 자신의 몸에 부딪히면 게임이 종료됩니다.
3. 방향 전환 처리
   방향 전환은 'L'이 입력되면 왼쪽으로 90도 회전, 'D'가 입력되면 오른쪽으로 90도 회전합니다. 이 과정은 시뮬레이션 시간과 방향 전환 정보를 비교하여 처리됩니다.

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

public class Main {
    static String[][] map;
    static int[] dr = {0, 1, 0, -1}; // 이동 방향: 동, 남, 서, 북
    static int[] dc = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 보드 크기
        int k = Integer.parseInt(br.readLine()); // 사과 개수
        map = new String[n][n];

        initMap(n); // 맵 초기화
        placeApples(br, k); // 사과 배치

        int l = Integer.parseInt(br.readLine()); // 방향 전환 횟수
        Queue<Dir> dirs = readDirections(br, l); // 방향 전환 정보

        System.out.println(simulateSnake(n, dirs));
    }

    static void initMap(int n) {
        for (int i = 0; i < n; i++) {
            Arrays.fill(map[i], "");
        }
    }

    static void placeApples(BufferedReader br, int k) throws IOException {
        for (int i = 0; i < k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            map[r][c] = "A"; // A는 사과를 의미
        }
    }

    static Queue<Dir> readDirections(BufferedReader br, int l) throws IOException {
        Queue<Dir> dirs = new LinkedList<>();
        for (int i = 0; i < l; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            String d = st.nextToken();
            dirs.add(new Dir(t, d));
        }
        return dirs;
    }

    static int simulateSnake(int n, Queue<Dir> dirs) {
        Deque<Pos> snake = new ArrayDeque<>();
        snake.add(new Pos(0, 0)); // 뱀 초기 위치
        map[0][0] = "S"; // S는 뱀을 의미

        int t = 0, r = 0, c = 0, dir = 0; // 시간, 좌표, 방향
        while (true) {
            t++;
            r += dr[dir];
            c += dc[dir];

            // 게임 종료 조건
            if (r < 0 || r >= n || c < 0 || c >= n || map[r][c].equals("S")) {
                return t;
            }

            // 사과가 있는 경우
            if (map[r][c].equals("A")) {
                snake.addLast(new Pos(r, c));
                map[r][c] = "S";
            } else { // 사과가 없는 경우
                Pos tail = snake.pollFirst();
                map[tail.r][tail.c] = ""; // 꼬리 이동
                snake.addLast(new Pos(r, c));
                map[r][c] = "S";
            }

            // 방향 전환
            if (!dirs.isEmpty() && t == dirs.peek().time) {
                dir = changeDir(dir, dirs.poll().dir);
            }
        }
    }

    static int changeDir(int dir, String turn) {
        if (turn.equals("D")) return (dir + 1) % 4; // 오른쪽 회전
        return (dir + 3) % 4; // 왼쪽 회전
    }

    static class Pos {
        int r, c;
        Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static class Dir {
        int time;
        String dir;
        Dir(int time, String dir) {
            this.time = time;
            this.dir = dir;
        }
    }
}