프로그래머스[JS] > 리코쳇 로봇

코딩테스트 연습 > 연습문제 > 리코쳇 로봇 (JS) 문제풀이

 

🔥문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

🔥풀이

처음에 DFS로 문제풀이 접근을 했는데 여러케이스에서 시간초과로 문제풀이에 실패했다. 그래서 다른 사람의 풀이를 봤는데 BFS로 문제에 접근하고 있었고 내 생각에도 이 접근법이 시간이 월등히 적게 들꺼란 생각이 들어 BFS로 다시 문제풀이를 진행했다. 

 

우리는 목표위치에 도달하기 위한 최소한의 미끄러짐 수를 구하기 때문에 굳이 모든 방식을 다 탐색할 필요없이 n번 움직였을 때 이동한 위치와 몇번 이동했는지 값만 기억하고 이동했던 포인트를 체크만 하면된다. (코드를 보면 알겠지만 한면 지나간 포인트는 visit_map에 표기하였다.) 

 

function solution(board) {
    
    let min = undefined
    let [start_x,start_y]=[undefined,undefined]    
    for(let i=0; i<=board.length-1; ++i){
        for(let j=0; j<=board[0].length-1; ++j){
            if(board[i][j]==='R'){
                start_x =i 
                start_y =j
            }
        }
    }
    
    let visit_map = Array.from({length:board.length},(_)=>{
        return Array(board[0].length).fill(false)
    })
    
    // 동서남북
    let dx =[0,0,1,-1] , dy =[1,-1,0,0]
    let queue = [[start_x,start_y,0]]
    visit_map[start_x][start_y]=true
        
    while(queue.length){
        let [x,y,count] = queue.shift()
        if(board[x][y]==='G'){
            min =count
            break;
        }
        dx.forEach((_,i)=>{
            // 동서남북 순
            let nx = x
            let ny = y 
            while(1){
                 nx += dx[i]
                 ny += dy[i]
                 if(!board[nx]||!board[nx][ny]||board[nx][ny]==='D'){
                     let [prev_x,prev_y] = [nx-dx[i],ny-dy[i]]
                     if(visit_map[prev_x][prev_y]===false){
                         queue.push([prev_x,prev_y,count+1])
                         visit_map[prev_x][prev_y]=true
                     }
                     
                     break;
                 }
            }
        })
    }
    
    return min === undefined ? -1 : min
    
}