[Graph - BFS, Medium] Nearest Exit from Entrance in Maze

https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/description/?envType=study-plan-v2&envId=leetcode-75

처음에는 그냥 단순하게 BFS로 풀었다.
visited로 중복은 최소화했고, 큐에 넣을 때마다 step 증가시켜서 최소 스텝을 리턴할 수 있게 했다.

그런데 아래 코드는 몇개 케이스에서 타임 리밋이 걸린다.
최적화가 필요하다.
최적화한 코드는 아래쪽에 있다.

class Solution {

    // 동서남북
    private int[] dy = {1, -1, 0, 0};
    private int[] dx = {0, 0, 1, -1};

    public int nearestExit(char[][] maze, int[] entrance) {
        
        int mazeX = maze.length;
        int mazeY = maze[0].length;

        boolean[][] visited = new boolean[mazeX][mazeY];

        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] {entrance[0], entrance[1], 0}); // int[] {x, y, step}

        while (!que.isEmpty()) {
            int[] current = que.poll();
            int curX = current[0];
            int curY = current[1];
            int step = current[2];

            visited[curX][curY] = true;

            boolean isEntrance = curX == entrance[0] && curY == entrance[1];
            boolean isBorder = (curX == 0 || curX == mazeX - 1) || (curY == 0 || curY == mazeY - 1);
            if (!isEntrance && isBorder && maze[curX][curY] == '.') {
                return step;
            }

            for (int i=0; i<4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (nextX < 0 || nextX >= mazeX || nextY < 0 || nextY >= mazeY) {
                    continue;
                }
                if (maze[nextX][nextY] == '+') {
                    continue;
                }
                if (visited[nextX][nextY]) {
                    continue;
                }
                que.offer(new int[] {nextX, nextY, step + 1});
            }
        }

        return -1;
    }
}

최적화할 수 있는 방법은 뭐가 있을까?

1. visited 체크를 큐에 넣을 때 처리
2. LinkedList 대신 ArrayDeque 사용
3. 시작지점인지 체크하는 isEntrance 변수를 매번 평가해서 만들지 않기
4. continue문으로 계속 끊지 말고 평가식을 합쳐 JVM이 최적화할 수 있도록 변경

위 내용을 각각 적용해봤을 때,
1번은 수정하지 않으면 문제 통과 자체가 되지 않는 크리티컬한 문제다. (탐색 범위자체가 다름)
나머지는 런타임 결과에 조금이지만 유의미한 감소를 이룬 것을 볼 수 있음.

최적화된 코드는 아래와 같다 (GPT 시켰더니 변수명도 달라짐)

class Solution {
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    public int nearestExit(char[][] maze, int[] entrance) {
        int rows = maze.length;
        int cols = maze[0].length;

        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();

        int startX = entrance[0], startY = entrance[1];
        queue.offer(new int[] {startX, startY, 0});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], steps = cur[2];

            if ((x != startX || y != startY) &&
                (x == 0 || x == rows - 1 || y == 0 || y == cols - 1)) {
                return steps;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols &&
                    maze[nx][ny] == '.' && !visited[nx][ny]) {

                    visited[nx][ny] = true;
                    queue.offer(new int[] {nx, ny, steps + 1});
                }
            }
        }

        return -1;
    }
}