문제

풀이 과정

요약

구현 문제. 큐를 활용했다.

상세

1. 사과를 먹으면 꼬리는 움직이지 않은체 머리만 이동한다. 빈공간이라면 머리와 꼬리는 동시에 움직인다. 뱀이 방향을 비트는 경우, 현재 머리와 꼬리가 어떻게 방향을 이동해야할지를 찾아내는 것 점 이 문제의 키이다.

2. 나의 경우, 머리와 꼬리를 아예 분리된 노드라고 생각하고 상황에 따라 따로 이동 시켜주는 것으로 문제를 해결했다.

3. 필요한 준비물을 다음과 같다.

   • class Snake : 입력값으로 들어오는 뱀이 방향을 변경하는 시간대와 어디로 돌아갈지의 방향 값.
   • Queue q : Snake 를 받기 위한 큐. 시간 순으로 입력값이 들어오므로, 정렬은 필요없기에 일반 큐를 사용함.
   • int[][] map : 뱀이 사용할 맵. 사과의 좌표도 함께 들어가 있다. (0 = 빈 공간, 1 = 뱀의 머리 혹은 꼬리, 2 = 사과)
   • int[] dr, dc : 뱀의 머리, 꼬리가 이동할 때 사용할 델타값
   • ArrayList headDirHistory : 시간마다 뱀의 머리 방향을 넣어놓는 리스트, 꼬리의 방향 값은 현재 뱀의 길이만큼 머리의 이전 방향 값이다. 따라서 머리 방향 데이터를 누적하면서 진행할 것이다.

4. 완전탐색을 돌린다. 게임은 인덱스에러가 나거나, 머리가 자기 몸에 부딪히면 끝이난다. 따라서 그만큼까지 탐색을 하면 된다.

정답

public class Main {
    static int N, K, L;
    static int[][] map;
    static StringTokenizer stk;
    static final int[] dr = new int[]{0, 1, 0, -1};
    static final int[] dc = new int[]{1, 0, -1, 0};

    static class Snake {
        int t;
        char dir;

        public Snake(int t, char dir) {
            this.t = t;
            this.dir = dir;
        }
    }

    static Queue<Snake> q = new LinkedList<>();
    static ArrayList<Integer> headDirHistory = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        map = new int[N][N];

        for (int i = 0; i < K; i++) {
            stk = new StringTokenizer(br.readLine());
            map[Integer.parseInt(stk.nextToken()) - 1][Integer.parseInt(stk.nextToken()) - 1] = 2;
        }

        L = Integer.parseInt(br.readLine());

        for (int i = 0; i < L; i++) {
            stk = new StringTokenizer(br.readLine());
            q.add(new Snake(Integer.parseInt(stk.nextToken()), stk.nextToken().charAt(0)));
        }


        int[] posH = new int[]{0, 0};
        int[] posT = new int[]{0, 0};
        // 뱀의 머리 방향과 꼬리 방향
        int[] currHTDir = new int[]{0, 0};
        int len = 1;
        map[0][0] = 1;
        int currT = 1;

        while (true) {
            headDirHistory.add(currHTDir[0]);
            currHTDir[1] = headDirHistory.get(currT - len);

            // 다음 머리 좌표
            int nhr = posH[0] + dr[currHTDir[0]];
            int nhc = posH[1] + dc[currHTDir[0]];

            if (nhr < 0 || nhc < 0 || nhr >= N || nhc >= N || map[nhr][nhc] == 1) {
                System.out.println(currT);
                return;
            }

            boolean isApple = false;
            if (map[nhr][nhc] == 2) isApple = true;

            posH[0] = nhr;
            posH[1] = nhc;
            map[posH[0]][posH[1]] = 1;

            if (isApple) len++;
            else {
                int ntr = posT[0] + dr[currHTDir[1]];
                int ntc = posT[1] + dc[currHTDir[1]];
                map[posT[0]][posT[1]] = 0;
                posT[0] = ntr;
                posT[1] = ntc;
            }

            if (!q.isEmpty() && q.peek().t == currT) {
                if (q.peek().dir == 'D') currHTDir[0] = (currHTDir[0] + 1) % 4;
                else currHTDir[0] = (currHTDir[0] + 3) % 4;
                q.poll();
            }
            currT++;
        }
    }
}