[JS] 미로탈출

BFS 와 que를 활용해서 풀었다. (지금 봤는데 중간에 변수 이름을 stk으로 썼는데 생각해보니 DFS가 아닌 BFS로 풀어야 하는 문제여서.. stk가 큐라고 생각하고 보면 좋을 것 같다.)

 

 

1. 시작 좌표 정하기

2. 방문했는지 정할 dp배열 정하기

=> 이때 레버있을때는 방문했던 곳을 또 지나갈 수 있으므로 레버가 없이 방문했으면 1, 없이 방문했으면 2를 넣어준다.

3. 큐에 첫 값으로 [시작 x좌표, 시작 y좌표, laver 유무 , 카운트] 를 넣어준다.

 

4. 큐를 순회하면서 갈 수 있는곳이라면 큐에 위에 정해준 서식대로 값을 넣어준다.

=> 레버를 당겼으면서 골인지점인 경우에는 cnt+1 을 출력

=> 레버가 당겼으면서 2번이상 방문한 곳은 큐에 더이상 넣지 않음

=> 레버가 당겨지지않은 경우는 1번이상 방문한 곳을 큐에 넣지 않음

 

그 외 경우는 방문했다고 기록을 한 후, 큐에 넣어주었다.

 

 

5. 만약 큐가 비어질때까지 return을 못만난다면 깰 수 없는 미로로 간주하고 -1을 반환

 

 

function solution(maps) {
    const dx = [1,0,-1,0]
    const dy = [0,1,0,-1]
    let S
    for (let i=0 ; i< maps.length ; i++) {
        for (let j=0; j<maps[0].length ; j++ ){
            if (maps[i][j]==='S') S = [j,i]
        }
    }
    const dp = [... new Array(maps.length)].map(_ => [... new Array(maps[0].length)].fill(0))
    const stk = [[...S,false,0]]
    dp[S[1]][S[0]]++
    
    while(stk.length){
        const [x,y,laver,cnt] = stk.shift()
        
        for (let k=0 ; k< 4 ; k++) {
            const [nx,ny] = [x + dx[k] , y + dy[k]]
            
            if (0<= nx && nx<maps[0].length && 0<= ny && ny< maps.length && maps[ny][nx]!=='X'){
                if ( laver && maps[ny][nx]==='E') return cnt+1
                if ( laver && dp[ny][nx]>1 ) continue
                if ( !laver && dp[ny][nx]>0 ) continue
                
                dp[ny][nx]++;
                stk.push([nx,ny,maps[ny][nx]==='L'?true:laver,cnt+1])
            }
        }
    }
    
    return -1
}