[백준 3190] 뱀 (Java, 골드4)

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

 

문제

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

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

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

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

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

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

 

 

시뮬레이션/구현 문제

문제에 나와있는 데로 구현하면 된다. 다만 그 구조가 인간의 직관적인 생각만으로는 쉬울 수 있어도, 코드가 끼얹어지면 어려워질 수 있다는 것이 구현 문제의 특징이다.

그렇다면, 알고리즘보다는 자료구조에 집중해보자

어떤 자료구조를 사용해서 뱀의 몸통 전체의 존재 위치와 머리/꼬리 부분을 저장할 것인지가 관건이다.

사과를 먹으면, 머리쪽이 늘어나고 (처음이 추가됨)

사과를 먹지 못하면, 꼬리쪽이 줄어든다. (마지막이 제거됨)

자료구조의 앞 혹은 뒤 둘다 데이터를 넣기도하고 빼기도 할 수 있어야 한다.

ArrayDeque

이 자료구조는 스택도 가능하고 큐도 가능해요!

데이터를 넣고 뺄 때, 앞/뒤 상관없이 원하는 끝에 자유자제로 입출력할 수 있는 자료구조이기 때문이다. 즉, 뱀이 늘어나면 큐의 헤드 부분을 늘리고(addFirst()), 뱀이 줄어들면 큐의 꼬리 부분을 줄이면(pollLast()) 된다.

그렇다면 시간 초가 지나가는 것은 어떻게 카운트할 것인가?

해쉬맵에 방향이 변화되는 초(seconds)를 key 값으로 넣어 식별하고, 값으로는 방향 정보를 저장하여 해당 초에 어떤 방향으로 변환했는지 저장해놓으면 된다.

뱀의 머리가 어느 방향을 향하고 있는가도 저장해야 했다.

현재 향하고 있는 방향과 움직이려는 방향(L/R)을 파라미터로 넣으면, 어느 방향으로 변하는지에 대한 메소드도 작성해야겠다. 매 방향마다 변하는 direction 이 다르기 때문이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int N;
    static int[][] map = null;
    static boolean[][] visited = null;
    static Map<Integer, String> movingPerSeconds = null;
    static int DIRECTION = 3; // 뱀의 머리가 향하고 있는 방향, 최초의 방향은 Right
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = getInt(br.readLine()); // 보드의 크기
        map = new int[N][N];
        visited = new boolean[N][N];

        int k = getInt(br.readLine()); // 사과의 개수
        for (int i=0; i<k; i++) {
            int[] apple = getIntArr(br.readLine().split(" "));
            map[apple[0]-1][apple[1]-1] ++;
        }

        int l = getInt(br.readLine()); // 뱀의 방향 변환 횟수
        movingPerSeconds = new HashMap<>();
        for (int i=0; i<l; i++) {
            String[] behavior = br.readLine().split(" ");
            int seconds = Integer.parseInt(behavior[0]);
            String direction = behavior[1];
            movingPerSeconds.put(seconds, direction);
        }

        System.out.println(simulation());
    }

    public static int simulation() {

        // 뱀의 이동경로
        // 뱀의 모든 몸통이 머리부터 시작해서 순서대로 저장되어 있다.
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.addLast(new int[]{0, 0}); // 최초의 머리 시작지점
        visited[0][0] = true;

//        printIntArr(map); // 사과 맵

        int sec = 0;
        while(true) {
            sec ++;

            // 현재 머리 좌표
            int[] xy = q.peekFirst();
            int x = xy[0];
            int y = xy[1];

            // 전진할 수 있다면 전진하라 (머리가 늘어난다)
            // 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
            int nx = x + dx[DIRECTION];
            int ny = y + dy[DIRECTION];

            // 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
            if (!canGoTo(nx, ny)) return sec;

            // 전진-!!
            // 머리가 늘어난다 (?)
            q.addFirst(new int[]{nx, ny});
            visited[nx][ny] = true;

            // (꼬리가 줄어들수도 있고 아닐 수도 있다)
            // 전진했는데 사과가 없는 경우
            // 꼬리가 줄어든다. q의 마지막이 poll 된다.]

            //  만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
            //  즉, 몸길이는 변하지 않는다.

            if (map[nx][ny] == 0) {
                int[] tail = q.pollLast();
                visited[tail[0]][tail[1]] = false;
            }

            // 4. 전진했는데 사과를 만난 경우

            // 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
            else {
                // 꼬리는 동일하며, 사과는 먹어치워 없어진다.
                map[nx][ny] = 0;
            }
//            print("sec=" + sec + ", DIR=" + DIRECTION + "\n");
//            printBoolArr(visited);


            // 방향을 틀어야 하면 방향을 틀어라
            if (movingPerSeconds.containsKey(sec)) {
                String moveTo = movingPerSeconds.get(sec);
                DIRECTION = getDirection(DIRECTION, moveTo);
            }

            x = nx;
            y = ny;
        }
    }

    /**
     * 해당하는 좌표로 갈 수 있는지 반환
     * @param x
     * @param y
     */
    public static boolean canGoTo(int x, int y) {
        // 새로 가려는 곳이 벽이거나(범위를 벗어나거나)
        if (x < 0 || x > N-1 || y < 0 || y > N-1) return false;
        // 이미 몸통이 있는 경우(visited = true)
        return !visited[x][y];
    }

    public static int getDirection(int direction, String moving) {
        switch (direction) {
            case 0 : // 상
                if (moving.equals("L")) return 2;
                else return 3;
            case 1 : // 하
                if (moving.equals("L")) return 3;
                else return 2;
            case 2 : // 좌
                if (moving.equals("L")) return 1;
                else return 0;
            case 3 : // 우
                if (moving.equals("L")) return 0;
                else return 1;
        }

        return -1;
    }

    static void print(String str) {
        System.out.print(str);
    }

    static void printIntArr(int[][] arr) {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void printBoolArr(boolean[][] arr) {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if(arr[i][j]) System.out.print("1 ");
                else System.out.print("0 ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static int getInt(String str) {
        return Integer.parseInt(str);
    }

    public static int[] getIntArr(String[] strArr) {
        return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
    }
}

 

부족했던 점

아무래도 구현 자체나 자료구조를 선정하고 해결해나가는 과정은 어렵지 않았는데, 나에게 있어서 부족한 부분은 시간 초가 지나가는 것과 같은 범위나 인덱싱 작업이었다. 그러한 사소한 차이들이 아직 어려운 것 같다. 그 부분에서 시간을 많이 끌었다. 더 세밀하게 신경써야할 것 같다.