Leet code (Medium) : 1926. Nearest Exit from Entrance in Maze (BFS) - JAVA

 

BFS의 대표적인 유형중 하나인, 빠른 탈출 문제이다.

메모리 효율을 위해 visited 객체를 따로 생성해서 쓰지않고 방문한 곳은 주어진 그래프에서 값을 업데이트 하는 방식으로 했다.

 

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

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrance);
        // 이렇게 지나온 곳을 장애물로 표시하고 지나가면 
        // visited 관련 객체를 따로 관리 하지 않아도돼서 메모리를 아낄수있음
        maze[entrance[0]][entrance[1]] = '+';

        int[] dr = new int[]{-1,0,0,1};
        int[] dc = new int[]{0,-1,1,0};

        int steps = 0;
        int row, col;

        // queue에 가까운 거리의 지점이 먼저 담기므로 목적지점에 도달했을때 지금까지 거리를 리턴하면 그게 최소거리임.
        // 목적지에 가는 순간 지금 까지 거리를 return 하면 그게 최솟값이 됨.
        while(!queue.isEmpty()){

            steps++;

            int n = queue.size();

            for(int i = 0; i < n; i++){
                int[] current = queue.poll();
                for(int j = 0; j < 4; j++){
                    row = current[0] + dr[j];
                    col = current[1] + dc[j];
                    
                    // maze를 벗어나거나
                    if(row < 0 || row >= rows|| col < 0 || col >= cols) continue;
                    // 장애물이면 다음으로 넘어감
                    if(maze[row][col] == '+') continue;

                    // 목적지점이면 지금까지 걸음을 리턴
                    if(row == 0 || row == rows-1 || col == 0 || col == cols-1) return steps;
                    
                    // 목적지점이 아니면 현 지점을 장애물 표시하고 현 지점에서 갈수 있는 지점들을 큐에 담음.
                    maze[row][col] = '+';
                    queue.offer(new int[]{row, col});
                }
            }
        }

        // while문을 도는 동안 목적지점을 찾지 못했다면 -1 리턴
        return -1;
    }
}