프로그래머스 [Lv. 2] 미로 탈출 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    
    let [Sr, Sc] = [0, 0];
    let [Er, Ec] = [0, 0];
    let [Lr, Lc] = [0, 0];
    
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            const mapsV = maps[i][j];
            if (mapsV == "S") {
                cnt += 1;
                [Sr, Sc] = [i, j];
            } else if (mapsV == "E") {
                cnt += 1;
                [Er, Ec] = [i, j];
            } else if (mapsV == "L") {
                cnt += 1;
                [Lr, Lc] = [i, j];
            } else {
                continue;
            };
            
            if (cnt == 3) {
                break;
            };
        };
        if (cnt == 3) {
            break;
        };
    };
    
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < m;
    };
    
    // 발상의 전환
    // 레버에서 출발하면 된다.
    // 순회가 끝나고 시작 지점과 출구의 visited값이 0이라면 갈 수 없다는 말이 된다.
    const q = [[Lr, Lc]];
    let visited = Array(n).fill().map(() => Array(m).fill().map(() => 0));
    visited[Lr][Lc] = 1;
    while (q.length) {
        const [r, c] = q.shift();
        for (let d = 0; d < 4; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (isValid(nr, nc) && maps[nr][nc] != "X" && visited[nr][nc] == 0) {
                visited[nr][nc] = visited[r][c] + 1;
                q.push([nr, nc]);
            };
        };
    };
    
    // 레버 부터 S와 E까지의 거리
    const distLS = visited[Sr][Sc];
    const distLE = visited[Er][Ec];
    
    const answer = distLS && distLE ? distLS + distLE - 2 : -1;
    return answer;
}

풀이 방법

1. 출구, 시작 지점, 레버의 위치를 찾는다.
2. 레버에서 출구와 시작 지점을 찾는 그래프 순회(BFS)를 시작한다.
3. 각 지점에 도달하면 자연수가 되어야 한다.
   1. 하지만 자연수가 아닌 0인 경우 래버를 이용해서 출구를 못 열었다는 말이 된다.
4. 두 지점 모두 자연수(양의 정수)라면 둘의 합에서 2를 뺀 값을 반환한다.
   1. 아닌 경우는 -1을 반환한다.

느낀점

• 쉽지만 자주 풀어보니까 요령이 생긴듯 하다.
• 처음 떠올린 것은 출발 지점에서 래버까지 갈 수 있는지 찾고 래버에서 다시 출구까지 순회를 해야한다.
• 결국 두 번 순회를 해야하는데 시간 복잡도는 2배가 될 것이고 효율도 떨어질 거라고 생각했다.