Description

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

---

1926. 미로 입구에서 가장 가까운 출구

여러분은 빈 칸( '.' 으로 표시됨)과 벽( '+' 으로 표시됨)이 있는 m x n 크기의 maze 미로를 주어진다. 또한, 미로의 시작점인 entrance 가 주어지는데, 여기서 entrance = [entrancerow, entrancecol] 는 처음에 서 있는 셀의 행과 열을 나타낸다.

한 번에 한 칸씩 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있다. 벽이 있는 셀로는 이동할 수 없으며, 미로 밖으로 나갈 수도 없다. 여러분의 목표는 entrance 에서 가장 가까운 출구까지의 최단 거리를 찾는 것이다. 출구는 미로의 경계에 있는 빈 셀로 정의된다. entrance 는 출구로 간주하지 않는다.

entrance 에서 가장 가까운 출구까지의 최단 거리에 있는 단계 수를 반환하거나, 그런 경로가 없으면 -1 을 반환한다.

예시 1:

입력: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
출력: 1
설명: 이 미로에는 [1,0], [0,2], [2,3]에 3개의 출구가 있다.
처음에는 입구 셀 [1,2]에 있다.

• [1,0]까지는 왼쪽으로 2단계 이동하여 도달할 수 있다.
• [0,2]까지는 위로 1단계 이동하여 도달할 수 있다.
  입구에서 [2,3]에 도달하는 것은 불가능하다.
  따라서 가장 가까운 출구는 [0,2]이며, 1단계 떨어져 있다.

예시 2:

입력: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
출력: 2
설명: 이 미로에는 [1,2]에 1개의 출구가 있다.
[1,0]은 입구 셀이므로 출구로 간주하지 않는다.
처음에는 입구 셀 [1,0]에 있다.

• [1,2]까지는 오른쪽으로 2단계 이동하여 도달할 수 있다.
  따라서 가장 가까운 출구는 [1,2]이며, 2단계 떨어져 있다.

예시 3:

입력: maze = [[".","+"]], entrance = [0,0]
출력: -1
설명: 이 미로에는 출구가 없다.

제약 조건:

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 는 '.' 또는 '+' 이다.
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance 는 항상 빈 셀이다.

Solution

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // Position 클래스는 미로 내의 위치와 해당 위치까지의 경로 길이를 저장합니다.
    class Position {
        int row;
        int col;
        int pathCount;  // 현재 위치까지 이동하는 데 필요한 단계 수

        Position(int row, int col, int pathCount) {
            this.row = row;
            this.col = col;
            this.pathCount = pathCount;  // 생성자를 통해 초기값 설정
        }
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        int shortestPathLength = Integer.MAX_VALUE;  // 최단 경로 길이를 저장할 변수, 초기값은 최댓값으로 설정
        Position entracneP = new Position(entrance[0], entrance[1], -1);  // 입구 위치 초기화

        int rowLength = maze.length;  // 미로의 행 길이
        int colLength = maze[0].length;  // 미로의 열 길이
        boolean[][] visited = new boolean[rowLength][colLength];  // 방문 여부를 추적하는 배열

        Queue<Position> queue = new LinkedList<>();  // BFS를 위한 큐
        queue.add(entracneP);  // 큐에 입구 위치 추가

        while (!queue.isEmpty()) {
            Position p = queue.poll();  // 큐에서 다음 위치를 가져옴

            // 미로의 경계에 도달했는지 확인
            if (p.row == -1 || p.row == rowLength || p.col == -1 || p.col == colLength) {
                if (p.pathCount != 0)  // 입구에서 바로 나가지 않았는지 확인
                    shortestPathLength = Math.min(shortestPathLength, p.pathCount);  // 최단 경로 업데이트
                continue;
            }

            // 현재 위치가 벽이면 더 이상 진행하지 않음
            if (maze[p.row][p.col] == '+') continue;

            // 현재 위치를 이미 방문했다면 더 이상 진행하지 않음
            if (visited[p.row][p.col]) continue;

            // 현재 위치를 방문한 것으로 표시
            visited[p.row][p.col] = true;

            // 상하좌우 위치를 큐에 추가
            queue.add(new Position(p.row - 1, p.col, p.pathCount + 1)); // 위로 이동
            queue.add(new Position(p.row + 1, p.col, p.pathCount + 1)); // 아래로 이동
            queue.add(new Position(p.row, p.col + 1, p.pathCount + 1)); // 오른쪽으로 이동
            queue.add(new Position(p.row, p.col - 1, p.pathCount + 1)); // 왼쪽으로 이동
        }
        // 최단 경로 길이 반환, 찾지 못했다면 -1 반환
        return shortestPathLength != Integer.MAX_VALUE ? shortestPathLength : -1;
    }
}