[프로그래머스] Lv2. 미로 탈출- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 미로 탈출

문제

제한사항

📌 내가 생각한 풀이

거쳐야하는 지점이 있으니, 나누어서 문제를 풀자

1. start지점에서, Lever지점까지 가는 최단경로
2. Lever지점에서, Exit지점까지 가는 최단경로
3. 만약 1번 or 2번 중에 하나라도 -1이면 -1을 리턴
4. 둘다 -1이 아니라면 합을 리턴

function solution(maps) {
    var answer = 0;
    let leverA = 0;
    let maps1 = maps.map((d)=>d.split(''));
    let maps2 = maps.map((d)=>d.split(''));
    let saero = maps.length;
    let garo = maps[0].length;
    let dx = [1,-1,0,0];
    let dy = [0,0,-1,1];
    let start = [];
    let lever = [];
    let goal = [];
    let renew = [];
    let queue2 = [];
    for(var i =0; i<saero; i++){
        for(var j =0; j<garo; j++){
            if(maps[i][j] === 'S') start.push([i,j]);
            else if(maps[i][j] === 'E') goal.push([i,j]);
            else if(maps[i][j] === 'L') lever.push([i,j]);
        }
    }
    
    let a = calc(start,maps1,lever);
    let b = calc(lever,maps2,goal);
    if(a === -1 || b === -1) return -1
    else return a+b;
    
}

const calc = (start, graph, end) =>{
    let answer = 0;
    let queue = [];
    let maps = graph;
    let dx = [1,-1,0,0];
    let dy = [0,0,1,-1];
    let garo = maps[0].length;
    let saero = maps.length;
    queue.push([start[0][0],start[0][1]])
    maps[start[0][0]][start[0][1]] = 1;
       while(queue.length > 0){
           
        let size = queue.length;
        for(var i =0; i<size; i++){
            let [x,y] = queue.shift();
            for(var j =0; j<4; j++){
                let nx = x+dx[j];
                let ny = y+dy[j];
                if(nx >=0 && nx <saero && ny >=0 && ny <garo && maps[nx][ny] !== 1 && maps[nx][ny] !== 'X'){
                    queue.push([nx,ny]);
                    maps[nx][ny] = 1;     
                }
                if(nx === end[0][0] && ny === end[0][1]){
                    return answer+1;
                }
        
            }
        }
        answer++;
    }
    return answer = -1
    
}

📌 느낀점

두 가지 경우로 나누어서 풀면 쉽게 풀리는 문제였다. DFS / BFS를 이용한 경로찾기 문제는 이제 이해가 되었고, 쉽게 풀렸다.