[LeetCode] 1926. Nearest Exit from Entrance in Maze, Medium

1. 문제

• 미로 정보가 .과 +로 주어질 때, .은 통로 + 벽으로 막혀있다. entrance 정보로 시작 위치가 주어질 때, 미로를 탈출할 수 있는 최소 이동 회수를 반환하라.
• entrance 좌표는 탈출구로 간주하지 않는다.

2. 해결

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function nearestExit(maze: string[][], entrance: number[]): number {
    const n = maze.length;
    const queue: number[][] = [[...entrance, 0]];

    const visited = Array.from({ length: n }, () => Array(maze[0].length).fill(false));


    while(queue.length) {
        const size = queue.length;

        const [x,y,step] = queue.shift();


        if((x!== entrance[0] || y !== entrance[1]) && (x === 0 || y ===0 || x === n-1 || y === maze[x].length - 1)) {
            return step;
        }
        for(let j = 0; j<4; j++) {
            const adjustX = dx[j] + x;
            const adjustY = dy[j] + y;

            if(adjustX >= 0 && adjustX < n && adjustY >=0 && adjustY < maze[adjustX].length
            && maze[adjustX][adjustY] === '.' && !visited[adjustX][adjustY]) {
                visited[adjustX][adjustY] = true;
                queue.push([adjustX, adjustY, step + 1]);
            }
        }
        
    }

    return -1;    
};

• 전형적인 BFS 문제. 다만, 실수한 점은 방문 체크를 큐에 넣기전에 해야하는데 이전에 해서 시간초과가 났다.
• 또, 큐에 step 정보를 물고다니기 때문에 레발 단위 순회를 할 필요가 없었는데 불필요한 레벨 단위 탐색을 했다는 점.