[프로그래머스 Level 2] 미로

이슈 링크

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을 반환합니다.