🖋️ 미로 탈출

# 문제 설명

1 x 1 크기의 칸들로 이루어진
직사각형 격자 형태의 미로에서 최대한 빠르게 탈출

• 조건
  

  • 각 칸은 통로 또는 벽으로 구성
    
    
  • 벽으로 된 칸은 지나가기 불가능
  • 통로로 된 칸으로만 이동 가능
  • 통로들 중 한 칸에는 미로를 빠져나가는 문 존재
    • 이 문은 레버를 당겨서만 열기 가능
  • 레버 또한 통로들 중 한 칸에 존재
    
    
  • 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여
    레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동
  • 이때 아직 레버를 당기지 않았더라도
    출구가 있는 칸을 지나가기 가능
    
    
  • 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때,
    최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하기

• 매개 변수
  

  • 미로를 나타낸 문자열 배열 maps

• 반환값
  

  • 미로를 탈출하는데 필요한 최소 시간을 return
  • 탈출할 수 없다면 -1을 return

• 📢 제한사항

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

• 📰 입출력 예시

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

• CODE

function solution(maps) {
    let start = [];  
    let lever = [];  
    
    const _maps = [[], []]; 
    
    for(let i=0; i<maps.length; i++) {
        _maps[0].push([]);
        _maps[1].push([]);
        for(let j=0; j<maps[i].length; j++) {
            _maps[0][i].push(maps[i][j]);
            _maps[1][i].push(maps[i][j]);
            if(maps[i][j] === "S") start = [i,j];
            else if(maps[i][j] === "L") lever = [i,j]
        }
    }
    
    const a = bfs(start, [..._maps[0]], "L");
    const b = bfs(lever, [..._maps[1]], "E");
    
    if(a === -1 || b === -1) return -1

    return a+b;
}

function bfs(start, arr, target) {
    let time = 0;                 
    const dx = [-1, 1, 0, 0];     
    const dy = [0, 0, -1, 1];
    const [n, m] = [arr.length, arr[0].length]    
    
    const q = [start];         
    arr[start[0]][start[1]] = 'X'; 
    while(q.length > 0) {
      
        const size = q.length;
        for(let i=0; i<size; i++) {
          
            const [x, y] = q.shift();
            for(let j=0; j<4; j++) {
                const nx = x + dx[j];
                const ny = y + dy[j];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] !== 'X') {
                    if(arr[nx][ny] === target) {
                         return time+1;
                    } 
                    q.push([nx, ny]);
                    arr[nx][ny] = 'X';
                }
            }
        }
        time++;
    }
    return -1;
}

풀이

• BFS 완전 탐색을 통해 solution 구하기
  
  
• _maps[0] 과 _maps[1] 는 배열 참조 문제 때문에 각각 선언
• 함수 내부에서 수정한 내용도 코드에서 배열을 수정하여 방문한 위치를 표시
  
  
• lever 와 start 의 좌표 구하기
• while 한 번 반복당 time++
  • L 이 target 일 때, E 가 target 일 때
    각각 최단거리 구하기
  • 지나간 경로는 'X'
  • 동서남북으로 이동하여 조건 상 맞으면 q.push()