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

문제링크

 

전형적인 최단거리 찾는 bfs 문제였습니다
최단 거리를 2번 찾아야 해서 함수를 만들어서 활용했습니다

특정 지점까지의 최단거리를 찾는 함수를 만들어서

1. 입구에서 레버까지 방문 가능 여부를 확인하고
2. 레버에서 출구까지 방문 가능 여부를 확인했습니다

 

function solution(maps) {
    const r_length = maps.length;
    const c_length = maps[0].length;
    const dr=[0,0,-1,1];
    const dc = [1,-1, 0,0];
    
    let visited = Array.from(new Array(r_length), ()=> new Array(c_length).fill(false));
    let q=[];
    
    let start;
    let lever;
    let end;
    let min_cnt=0;
    
    //시작, 출구, 레버 위치 구하기
    for(let r=0;r<r_length;r++){
        for(let c=0;c<c_length;c++){
            if(maps[r][c]==='S') start=[r, c];
            if(maps[r][c]==='E') end=[r,c];
            if(maps[r][c]==='L') lever=[r,c];
        }
    }
    
    //최단거리 bfs
    //출발지점에서 레버까지 거리 구하기
    q.push({pos:start, cnt:0});
    visited[start[0]][start[1]]=true;
    
    //레버까지 도달할 수 없으면 -1
    if(!find_route('L')) return -1;
    
    //레버에서 출구까지 거리 구하기
    q.push({pos:lever, cnt:0});
    visited[lever[0]][lever[1]]=true;
    
    //출구까지 도달할 수 없으면 -1
    if(!find_route('E')) return -1;
    
    function find_route(finish){
        
        //bfs로 구하기
        //q가 빌 때까지 반복
         while(q.length){
            const {pos, cnt}=q.shift();
            const current_r=pos[0];
            const current_c =pos[1];
         
            //목적지까지 도달하면 min_cnt 업데이트하고 q랑 visited 배열 다시 설정
            if(maps[current_r][current_c]===finish){
                min_cnt+=cnt;
                q=[];
                visited=Array.from(new Array(r_length), ()=> new Array(c_length).fill(false));
                return true;
            }

            for(let i=0;i<4;i++){
                const next_r  = current_r+dr[i];
                const next_c = current_c+dc[i];

                //벽이 아니고 방문하지 않은 통로만 큐에 넣기
                if(next_r>=0&&
                  next_r<r_length&&
                  next_c>=0&&
                  next_c<c_length&&
                  maps[next_r][next_c]!=='X'&&
                   !visited[next_r][next_c]
                  ){
                    q.push({pos:[next_r, next_c], cnt:cnt+1});
                    visited[next_r][next_c]=true;
                }
            }
        
        }
        return false;
    }
    
   
    return min_cnt;
   
}