[알고리즘 TIL] Q3190(자료구조)

문제

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

트러블 슈팅

1. 뱀의 꼬리 저장 - Queue 자료구조 이용

처음에는 단순히 뱀의 머리 위치만 관리하며 이동했지만, 사과를 먹을 때는 꼬리가 움직이지 않아야 하며, 사과를 먹지 않으면 꼬리가 한 칸 줄어들어야 한다. 따라서 머리뿐만 아니라 꼬리까지 추적해야함을 깨달았고, 이를 위해 뱀의 꼬리를 저장하는 변수를 따로 선언했다. 그리고, 뱀의 꼬리는 매번 이전 꼬리의 사방을 확인하여 뱀의 몸통이 있는 좌표를 꼬리로 갱신하였다.

for (int i = 0; i < 4; i++) {
     if (board[tailY + dy[i]][tailX + dx[i]] == SNAKE) {
         tailY += dy[i];
         tailX += dx[i];
     }
}

하지만 이전 꼬리의 사방 중 뱀의 몸통이 단 하나라는 보장이 없어서 오류가 난다. 

 

큐를 이용해 뱀의 몸통을 저장하면, 큐에서 poll하여 뱀의 꼬리를 간단하게 관리할 수 있게 된다.

• 머리를 이동할 때마다 queue.add(머리 위치)
• 사과를 먹지 않았을 경우 queue.poll()을 통해 꼬리 좌표를 꺼내고 해당 좌표를 EMPTY로 갱신

2. null 예외 처리 순서 오류

처음에는 ny += dy로 머리를 먼저 이동시킨 뒤, 바로 board[ny][nx]를 조회했다. 그런데 ny, nx가 보드 범위를 벗어난 경우, 배열 접근 자체에서 ArrayIndexOutOfBoundsException 혹은 NullPointerException이 발생했다.

ny += snakeDy;
nx += snakeDx;
if (board[ny][nx] == SNAKE)

이동 직후에는 항상 먼저 유효한 위치인지 검사해야 한다. 즉, board[][]에 접근하기 전에 checkIsAbleToMove()를 먼저 호출하여 좌표가 범위 내에 있는지 확인한 뒤, 그 다음 동작을 수행해야 한다.

ny += snakeDy;
nx += snakeDx;

if (!checkIsAbleToMove(ny, nx)) break;

저번에도 같은 실수를 했는데... 유의해야겠다.

코드

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

public class Q3190 {

    static int[][] board;
    static final int EMPTY = 0, APPLE = 1, SNAKE = 2;
    static HashMap<Integer, String> directionChange;
    static HashSet<Integer> changeSecond;
    static int snakeDy = 0;
    static int snakeDx = 1;
    static int time = 0;
    static int n;

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

        n = Integer.parseInt(br.readLine());
        board = new int[n][n];

        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            String[] inputStrArr = br.readLine().split(" ");
            int appleRow = Integer.parseInt(inputStrArr[0]);
            int appleCol = Integer.parseInt(inputStrArr[1]);
            board[appleRow-1][appleCol-1] = APPLE;
        }

        int l = Integer.parseInt(br.readLine());
        directionChange = new HashMap<>();
        changeSecond = new HashSet<>();
        for (int i = 0; i < l; i++) {
            String[] inputStrArr = br.readLine().split(" ");
            int second = Integer.parseInt(inputStrArr[0]);
            String direction = inputStrArr[1];
            directionChange.put(second, direction);
            changeSecond.add(second);
        }
        // 머리 위치 정보
        int ny = 0;
        int nx = 0;

        board[ny][nx] = SNAKE;
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(new Integer[]{ny,nx});

        while (true) {
            time++;
            ny += snakeDy;
            nx += snakeDx;
            if(!checkIsAbleToMove(ny, nx)) break;
            if (board[ny][nx]==APPLE) {
                //사과를 먹은 경우 이동
                board[ny][nx] = SNAKE;
                queue.add(new Integer[]{ny,nx});
            } else {
                //사과를 안 먹은 경우 이동
                Integer[] poll = queue.poll();
                board[poll[0]][poll[1]] = EMPTY;
                board[ny][nx] = SNAKE;
                queue.add(new Integer[]{ny,nx});
            }
            checkIsTimeToChangeDirection();
        }

        bw.write(time+"");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void checkIsTimeToChangeDirection() {
        if (changeSecond.contains(time)) {
            String direction = directionChange.get(time);
            int temp;
            switch (direction) {
                case "D":
                    temp = snakeDy;
                    snakeDy = snakeDx;
                    snakeDx = -temp;
                    break;
                case "L":
                    temp = snakeDy;
                    snakeDy = -snakeDx;
                    snakeDx = temp;
            }
        }
    }

    private static boolean checkIsAbleToMove(int ny, int nx) {
        if (ny > n - 1 || ny < 0 || nx < 0 || nx > n - 1) return false;
        if (board[ny][nx]==SNAKE) return false;
        return true;
    }
}