코딩테스트 - 미로 탈출

최단거리를 찾는 문제로 bfs (너비우선탐색) 알고리즘 문제이다.
자료구조 큐를 사용하는 문제로 탐색 후 갈수 있는 경로를 큐에 넣고 순서대로 탐색.

처음 코드 작성 시 방문 체크를 해당 노드에서 탐색을 시작하기 전 시점으로 잡았다가 시간 초과로 틀렸었고 체크 시점을 탐색 되었을 시점으로 변경

function solution(maps) {
    let answer = 0;
    let start = [];
    let ll = [];
    for (let i = 0 ; i < maps.length; i++){
        for (let j =0; j < maps[0].length; j++){
            let now = maps[i][j];
            if(now == "S"){
                start = [i,j];
            }else if(now == "L"){
                ll = [i,j];
            }
        }
    }

    
    let StoL = bfs(maps, start[0], start[1], "L");

    if(StoL == -1){
        return -1;
    }else{
        answer += StoL;
    }

    let LtoE = bfs(maps, ll[0] ,ll[1] ,"E");
    if(LtoE == -1){
        return -1;
    }else{
        answer += LtoE;
    }
    return answer;
}

function bfs(maps, x ,y , findalp){
   
    const maxx = maps.length;
    const maxy = maps[0].length;
    const q = [[x,y,0]];
    const xm = [1,0,-1,0];
    const ym = [0,1,0,-1];
    const visited = [];
    for (let i = 0 ; i < maxx; i ++){
        let visited2 =  new Array(maxy).fill(false);
        visited.push(visited2);
    }
    visited[x][y] = true;
    while(q.length != 0){
        const [x,y,cnt] = q.shift();
        // 첫 코드 작성 시 방문 체크 시점
        // visited[nx][ny] = true;
        for (let i = 0 ; i<4; i++){
         
            let nx = x+xm[i];
            let ny = y+ym[i];
 
            
            if(nx>=0 && nx<maxx && ny>=0 && ny<maxy && !visited[nx][ny] & maps[nx][ny] != "X"){
                if(maps[nx][ny] == findalp){
                    return cnt+1;
                }
                q.push([nx,ny,cnt+1]);
                // 탐색 되었을 때 방문 체크
                visited[nx][ny] = true;
            }
            
        }
        
    }
    return -1;
    
}