백준 3190 번 : 뱀 풀이(Java)

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

3190번: 뱀

시간이 이것보단 길게 나올 줄 알았는데 의외였다.

Key Point

1. 뱀의 머리는 기본적으로 정해진 방향대로 이동한다.

2. 사과를 먹었을 때는 꼬리를 고정해두고, 먹지 못했다면 꼬리를 머리 쪽으로 당겨야 한다.

3. 이게 중요한데, 사과를 먹었다면 먹은 걸로 처리를 해줘야한다. (안 해주면 23% 에서 틀리는 것 같다.)

 

해법

뱀의 상태, 즉 뱀이 차지하고 있는 칸들을 Deque 에 담아 준다. front 와 rear 모두 삽입과 삭제가 가능한 만큼 최적의 자료구조일 것이다. 뱀의 상태를 나타낼 생각을 안하고, 뱀이 방향을 꺾을 때 마다 관절 부분들을 덱에 넣는 방식을 채택했다가 시간을 많이 잡아먹었다. 역시 아직도 많이 부족함을 느낀다.

 

1. 입력을 받는다. (받으면서 사과는 map에 다르게 표시를 해준다)

1-1. 뱀의 상태를 나타내는 snake 덱에 시작 위치인 (0,0) 의 Node 를 담는다.

2. 무한 루프를 돌면서 

2-1. 뱀의 머리의 다음 위치는 현재 뱀 머리의 위치에, 뱀이 바라보고 있는 방향이다.

int hx = head.x;
int hy = head.y;
checkChangeDir();
int nx = hx + dx[snakeDir];
int ny = hy + dy[snakeDir];

다음 위치를 바라보기 전에, 방향을 바꿔야 하는지 체크하고 필요하다면 바꿔준 뒤에 이동한다.

2-2. 만약에 다음 위치가 map 을 벗어나거나, 자신의 몸 부분이라면 break 해준다.

2-2-1. 만약 둘 다 아니라서 이동이 가능한 경우, 머리는 어차피 이동 하므로 다음 위치를 snake 의 rear 에 추가해준다.

2-2-1-1 . 다음 위치가 사과일 경우, 다음 위치는 사과를 먹은 후의 상태로 초기화를 해준다.

2-2-1.2 . 다음 위치가 사과가 아닐 경우, 기존의 꼬리를 떼준다.

 

전체 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N,K,L, snakeDir, count;
    static short[][] map;
    static Deque<Node> snake;
    static Deque<Movement> movements;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1}; // 상, 우, 하, 좌

    static class Node {
        int x;
        int y;

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

    static class Movement {
        int time;
        char dir;

        public Movement(int time, char dir) {
            this.time = time;
            this.dir = dir;
        }
    }

    static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        K = Integer.parseInt(bufferedReader.readLine());
        map = new short[N][N];
        movements = new ArrayDeque<>();
        snake = new ArrayDeque<>();
        snake.addLast(new Node(0,0));
        count = 0;
        snakeDir = 1; // 오른쪽 방향을 보고 시작
        for(int i = 0; i < K; i++) {
            StringTokenizer xy = new StringTokenizer(bufferedReader.readLine());
            int x = Integer.parseInt(xy.nextToken()) - 1;
            int y = Integer.parseInt(xy.nextToken()) - 1; // input 이 1,1 부터 시작하는 기준이라서 1씩 빼준다.
            map[x][y] = 1;
        }
        L = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < L; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            movements.offer(new Movement(Integer.parseInt(st.nextToken()),  st.nextToken().charAt(0)));
        }
    }

    static boolean isOut(int nx, int ny) {
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
            return true;
        }
        return false;
    }

    static boolean isSelfBody(int nx, int ny) {
        for(Node n : snake) {
            if(n.x == nx && n.y == ny) {
                return true;
            }
        }
        return false;
    }

    static void checkChangeDir() {
        if(!movements.isEmpty() && movements.peekFirst().time + 1 == count) {
            Movement m = movements.pollFirst();
            if(m.dir == 'D') {
                snakeDir = (snakeDir + 1) % 4;
            } else {
                if(snakeDir == 0) {
                    snakeDir = 3;
                } else {
                    snakeDir -= 1;
                }
            }
        }
    }

    static boolean isApple(int nx, int ny) {
        return map[nx][ny] == 1;
    }

    static void solve() {
        while (true) {
            ++count;
            Node head = snake.peekLast();
            Node tail = snake.peekFirst();
            int hx = head.x;
            int hy = head.y;
            checkChangeDir();
            int nx = hx + dx[snakeDir];
            int ny = hy + dy[snakeDir];
            if(isOut(nx, ny) || isSelfBody(nx, ny)) {
                break;
            }
            snake.addLast(new Node(nx, ny));
            if(!isApple(nx, ny)) {
                snake.pollFirst();
            } else {
                map[nx][ny] = 0;
            }
        }
        System.out.println(count);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}