[프로그래머스]미로 탈출

문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

풀이

1. 레버를 돌려야 문이 열리기 때문에 레버까지 가는 데 걸리는 최소시간과 레버에서 출구까지 가는 데 걸리는 최소시간을 더해서 정답을 도출해야 한다.
2. 중복체크를 위한 맵과 시간을 체크하기 위한 방문배열을 생성해 레버까지 가는 bfs와 출구까지 가는 bfs를 돌린다.
3. 레버까지 도달했을 때 그 값이 0이라면 레버까지 도달하지 못한 것이기 때문에 -1을 리턴하고 0이 아니면 정답에 해당 시간을 더한다.
4. 출구까지 도달했을 때 값이 0이면 출구까지 도달하지 못한 것이기 때문에 -1을 리턴하고 0이 아니면 정답에 해당 시간을 더해서 정답을 리턴한다.

코드

function solution(maps) {
    let answer = 0;
    let dupMap = maps.map(v => v.split(""));
    let lMap = maps.map(v => v.split(""));
    const visited = Array.from(Array(maps.length), () => Array(maps[0].length).fill(0));
    const lVisited = Array.from(Array(maps.length), () => Array(maps[0].length).fill(0));
    for(let i=0; i<maps.length; i++){
        for(let j=0; j<maps[0].length; j++){
            if(maps[i][j] == 'S')  bfs(i, j, dupMap, visited);
            if(maps[i][j] == 'L') bfs(i ,j, lMap, lVisited);
        }
    }
    
    for(let i=0; i<maps.length; i++){
        for(let j=0; j<maps[0].length; j++){
             if(maps[i][j] == 'L') {
                if(visited[i][j] == 0) return -1;
                answer += visited[i][j];
            }
            if(maps[i][j] == 'E'){
                if(lVisited[i][j] == 0) return -1;
                answer += lVisited[i][j];
            } 
        }
    }
    return answer;
}

  

 const bfs = (sx,sy, maps, visited) => {
    let dx = [-1,1,0,0];
    let dy = [0,0,-1,1];

    const q = [[sx, sy]];

    while(q.length){
    const [x,y] = q.shift();
        for(let i=0; i<4; i++){
            const nowX = x + dx[i];
            const nowY = y + dy[i];

            if(nowX < 0 || nowY < 0 || nowX >= maps.length || nowY >= maps[0].length) continue;
            if(maps[nowX][nowY] != 'X'){
                q.push([nowX, nowY]);
                maps[nowX][nowY] = 'X';
                visited[nowX][nowY] = visited[x][y] + 1;
            }
        }
    }
}