[백준] 3190. 뱀 (Java)

deque (double-ended queue)를 사용하면 손쉽게 구현 가능한 문제

 

3190번: 뱀

 

풀이

우선 문제를 꼼꼼히 잘 읽어야 한다!

X초와 방향전환 정보가 주어지는데 게임 시작 시간으로부터 X초가 끝난 뒤 방향 전환을 한다.

 

이동시 snake의 tail을 head로 한 칸씩 옮겨가면 된다.

앞, 뒤 insert가 용이한 deque를 사용했다.

 

Java에서의 deque method는 snake에 대조해보면 다음과 같다.

 

 

소스코드를 실제로 돌려보니 deque 상에선 snake head가 tail이 되고 snake tail이 head여서 헷갈리므로 유의해야 한다.

 

Logic

• getDirection: 현재 뱀이 향하고 있는 방향 정보, L/D 값 중 하나를 받아 다음 방향 정보 반환
• isIn: 벽 또는 자기 자신 몸통에 부딪히면 false 반환

1. 사과의 위치는 2차원 배열 map에 APPLE 상수값으로 저장하고 시간별 L/D 정보를 입력받는다. 이때 char값을 int형으로 변환하여 저장해두었다.
2. time을 1 증가시킨다. 다음 방향이 벽이거나 snake body면 반복문을 빠져나온 후 time값을 출력한다.
3. 다음 방향에 사과가 있지 않으면 snake의 tail을 자른다. (map에서 해당 위치를 0으로 마킹하고 poll())
4. 앞으로 나아가기 위해 map에 SNAKE라고 마킹을 하고 deque에 snake의 head 정보를 추가한다.
5. 현재 시간이 방향 전환해야할 시간이 되면 getDirection method로 다음 방향 정보를 받아온다.
6. 2~5를 반복한다.

 

코드

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

public class Main {
    static final int APPLE = 5, SNAKE = 1;
    static int N, K, L, time;
    static int[][] map;
    static int[][] order;
    static int[] pos_x = { 0, -1, 0, 1 };
    static int[] pos_y = { 1, 0, -1, 0 };
    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(time);
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N + 2][N + 2];
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = APPLE;
        }

        L = Integer.parseInt(br.readLine());
        order = new int[L + 2][2];
        for (int i = 1; i <= L; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int d = 0;
            char temp = st.nextToken().charAt(0);
            if (temp == 'L') d = 0;
            else d = 1;

            order[i][0] = x; 
            order[i][1] = d; 
        }

        br.close();
    }

    public static void solve() {
        int idx = 1;
        Deque<Snake> snake = new LinkedList<>();

        snake.add(new Snake(1, 1, 0));
        map[1][1] = SNAKE;
        outer:
            while (true) {
                int px = snake.peekLast().x;
                int py = snake.peekLast().y;
                int d = snake.peekLast().d;
                int nx, ny;

                nx = px + pos_x[d];
                ny = py + pos_y[d];

                time++;
                if (!isIn(nx, ny)) break outer;
                if (map[nx][ny] == 0) {
                    int lx = snake.peek().x;
                    int ly = snake.peek().y;
                    map[lx][ly] = 0;
                    snake.poll();
                }
                map[nx][ny] = SNAKE;
                snake.add(new Snake(nx, ny, d));
                px = nx;
                py = ny;

                if (order[idx][0] == time)
                    snake.peekLast().d = getDirection(snake.peekLast().d, order[idx++][1]);
            }
    }

    public static boolean isIn(int x, int y) {
        if (x < 1 || x > N || y < 1 || y > N || map[x][y] == SNAKE)
            return false;

        return true;
    }

    public static int getDirection(int prev, int d) {
        int next = 0;

        switch(prev) {
        case 0:
            if (d == 0) next = 1;
            else next = 3;
            break;
        case 1:
            if (d == 0) next = 2;
            else next = 0;
            break;
        case 2:
            if (d == 0) next = 3;
            else next = 1;
            break;
        case 3:
            if (d == 0) next = 0;
            else next = 2;
            break;
        }

        return next;
    }

    static class Snake {
        int x;
        int y;
        int d;

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

 

 

실행 결과