[프로그래머스] 미로 탈출 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(maps) {
    maps = maps.map(m => m.split(""));
    const drow = [-1, 1, 0, 0];
    const dcol = [0, 0, -1, 1];
    let sr, sc, er, ec, lr, lc;
    for (let i = 0; i < maps.length; i += 1) {
        for (let j = 0; j < maps[0].length; j += 1) {
            if (maps[i][j] === "S") [sr, sc] = [i, j]; // 시작 위치
            else if (maps[i][j] === "E") [er, ec] = [i, j]; // 탈출 위치 
            else if (maps[i][j] === "L") [lr, lc] = [i, j]; // 레버 위치
        }
    }
    let cmaps = maps.map(m => m.slice());
    const q = []
    const bfs = (r, c, v) => {
        q.push([r, c])
        cmaps[r][c] = v
        while (q.length) {
            const [a, b] = q.shift()
            for (let i = 0; i < 4; i += 1) {
                const [dr, dc] = [a + drow[i], b + dcol[i]]
                if (dr < 0 || dc < 0 || dr >= maps.length || dc >= maps[0].length) continue
                if (cmaps[dr][dc] === "X" || cmaps[dr][dc] < 10000) continue
                else {
                    cmaps[dr][dc] = cmaps[a][b] + 1
                    q.push([dr, dc]);
                } 
            }
        }
        return cmaps
    }
    let t = bfs(sr, sc, 0)[lr][lc]
    if (t !== "L") { // L 진입 가능한 경우
        cmaps = maps.map(m => m.slice()); // 맵 초기화
        t = bfs(lr, lc, t)[er][ec] // E 진입시도
    } else return -1
    return t !== "E" ? t : -1
}

구현 로직 (BFS)

레버를 먼저 도달해야하는 조건 때문에 bfs를 두번 사용해야 합니다. 레버를 찾으러 1번, 레버부터 탈출구까지 1번 시도됩니다.

레버를 찾은 경우에는 bfs시작점을 레버의 위치로 지정하고 레버를 찾지 못한 경우 -1을 그대로 반환합니다.

레버는 찾았지만 탈출구까지 진입을 못하는 경우도 -1을 반환합니다.

탈출구로 진입한 경우 탈출구에 해당하는 값을 반환합니다.

 

1. 시작/탈출/레버 위치 저장

2. 레버 목표 BFS 시도

3. 탈출구 목표 BFS 시도

4. 탈출구 값 반환

 

※ maps길이가 10000 넘어가면 JS로는 답 없습니다. 큐를 직접 작성해서 쓰거나 Python으로 푸시길..