[프로그래머스 Level 2] 미로 탈출 - JavaScript

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

✏️ 풀이

function solution(maps) {
    const offset = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const xLen = maps.length;
    const yLen = maps[0].length;
    
    const bfs = ([sx, sy], [ex, ey]) => {
        const visited = Array.from({ length: xLen }, () => Array(yLen).fill(false));
        visited[sx][sy] = true;
        let queue = [{ x: sx, y: sy, count: 0 }];
        
        while (queue.length) {
            const stack = queue;
            queue = [];
            while (stack.length) {
                const { x, y, count } = stack.pop();
                
                if (x === ex && y === ey) {
                    return count;
                }
                
                offset.forEach(([dx, dy]) => {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (
                        nx >= 0 && nx < xLen && ny >= 0 && ny < yLen
                        && !visited[nx][ny]
                        && maps[nx][ny] !== 'X'
                    ) {
                        visited[nx][ny] = true;
                        queue.push({ x: nx, y: ny, count: count + 1 });
                    }
                });
            }
        }
        
        return -1;
    };
    
    let start, lever, exit;
    
    for (let i = 0; i < xLen; i++) {
        for (let j = 0; j < yLen; j++) {
            switch (maps[i][j]) {
                case 'S':
                    start = [i, j];
                    break;
                case 'L':
                    lever = [i, j];
                    break;
                case 'E':
                    exit = [i, j];
            }
        }
    }
    
    const startToLever = bfs(start, lever);
    
    if (startToLever === -1) {
        return -1;
    }
    
    const leverToExit = bfs(exit, lever);
    
    if (leverToExit === -1) {
        return -1;
    }
    
    return startToLever + leverToExit;
}

먼저 시작 지점, 레버, 출구의 위치를 찾는다. 시작 지점으로부터 레버까지의 최단거리 + 레버로부터 출구까지의 최단거리를 합하면 미로를 탈출하는데 필요한 최소 시간을 구할 수 있다. 이 때, 시작 지점으로부터 레버까지 도달할 수 없거나 레버로부터 출구까지 도달할 수 없으면 -1을 반환하면 된다.