BOJ) 뱀 (3190번)

뱀

3190번: 뱀

 

시뮬레이션 문제로 기억하는 사람이 있을지 모르지만, 피자를 먹으면 뱀의 꼬리가 늘어나는 게임이 있었다.

딱, 그 문제를 구현하는 문제였다.

아무튼, 행과 열을 오랜만에 이용하다보니 이에 대한 개념의 혼동으로 문제를 틀렸었다.

행은 가로에 대한 정보, 열은 세로에 대한 정보다.

따라서, 행은 y축의 index를 가지고 열은 x축의 index를 갖게된다.

 

풀이

문제의 조건에 머리가 뱀의 몸에 닿거나 벽에 닿으면 종료된다.

벽에 대한 정보를 저장해주려고 맵의 크기를 N+2로 지정해서 초기화해줬다. (이 부분은 out of index로 처리해도 좋다)

뱀의 초기 위치를 1,1로 선언하고, 초기 방향을 오른쪽으로 설정해줬다.

방향은 정수형으로 선언해서 0,1,2,3의 값을 가지게 했다. (0: 북, 1: 동, 2: 남, 3: 서)

 

시간에 따라 이동하면서, 다음 머리의 위치가 몸통이나 벽에 닿는지 확인해준다.

이후, 사과가 맵에 있는지 아닌지 판단해서 뱀의 정보를 담고있는 꼬리에 대한 조작을 해준다.

LinkedList로 선언해서 머리를 항상 처음에 위치시키고, 꼬리를 끝에 위치시키게 해주었다.

방향 전환은 mod 연산을 사용해서 방향의 최댓값인 3을 넘지 않게했고, 음수인지 검증하여 최솟값인 0을 넘어가지 않도록 설정해주었다.

이외에는 특이점이 없는 것 같다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Snake_3190 {
    final static char WALL = 'W', APPLE ='A', SNAKE ='S', SPACE = ' ', LEFT = 'L', RIGHT = 'D';
    final static int directionLength =4, MAX_TIME = 10000, TURN_LEFT = -1, TURN_RIGHT =1;
    final static Pos[] directionMove= { new Pos(0,-1), new Pos(1,0), new Pos(0,1), new Pos(-1,0)}; // 0 북, 1 동 2 남 3 서

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

        int k = Integer.parseInt(br.readLine()); // 사과 개수 K
        StringTokenizer st;
        while(k >0) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());   // 행의 위치
            int x =  Integer.parseInt(st.nextToken());  // 열의 위치
            map[y][x] = APPLE;
            k--;
        }

        int l = Integer.parseInt(br.readLine());
        char[] commands = new char[MAX_TIME+1];
        for(int i=0; i<l; i++) {
            st = new StringTokenizer(br.readLine());
            commands[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
        }
        br.close();
        solution(map, commands);
    }

    private static char[][] initMap(int n) {
        char[][] map = new char[n+2][n+2];
        Arrays.fill(map[0], WALL);
        Arrays.fill(map[n+1], WALL);
        for(int i=1; i<=n; i++) {
            Arrays.fill(map[i], SPACE);
            map[i][0] = WALL;
            map[i][n+1] = WALL;
        }
        map[1][1] = SNAKE;
        return map;
    }

    private static void solution(char[][] map, char[] commands) {
        int answer =0;
        int direction = 1; // 오른쪽을 보는 방향으로 시작
        LinkedList<Pos> snake = new LinkedList<>();
        snake.offer(new Pos(1,1)); // 초기 뱀 위치
        while(answer < MAX_TIME) {
            answer++;
            Pos now = snake.peek();
            Pos next = new Pos(now.x + directionMove[direction].x, now.y + directionMove[direction].y);
            // 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
            if(map[next.y][next.x] == WALL || map[next.y][next.x] == SNAKE) { // 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
                break;
            }
            if(map[next.y][next.x] != APPLE) { // 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
                Pos tail = snake.pollLast();
                map[tail.y][tail.x] = SPACE;
            }
            // 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
            snake.offerFirst(next);
            map[next.y][next.x] = SNAKE;


            if(commands[answer] == LEFT) {
                direction = getDirection(direction, TURN_LEFT);
            } else if(commands[answer] == RIGHT) {
                direction = getDirection(direction, TURN_RIGHT);
            }
        }
        System.out.println(answer);
    }

    private static int getDirection(int direction, int turn) {
        int next = (direction + turn) % directionLength;
        return next <0 ? next+directionLength : next;
    }

    private static class Pos {
        int x, y;

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