[프로그래머스] 리코쳇 로봇 - Javascript

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

 

문제 요약 :

1. 격자 위에서 상하좌우로 로봇이 이동할 수 있다.
2. 대신 로봇은 한번 이동한 순간 격자의 벽면 혹은 장애물을 만날 때까지 계속 이동한다.
3. 로봇이 멈춘 순간, 목표지점에 도달하는 가장 최소 이동 거리를 구하라

 

문제 풀이 시간 : 30분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. bfs로 상하좌우 탐색 + 도착 칸의 최소 비용 갱신

 

현재 위치에서 상하좌우로 이동하면 되고, 장애물이나 벽을 만날 때까지 해당 방향으로 계속 ++ 해주면 될 것 같다.

또한, 왔던 곳을 다시 오지 않기 위해 도착 칸마다 최소 비용을 갱신해주면 될 것 같다.

전체 코드(성공) :

function solution(board) {
    const row = board.length; // 격자의 크기
    const col = board[0].length;
    
    const Ri = 0, Rj = 0; // 출발 좌표
    
    for(let i=0; i<row; i++){
        for(let j=0; j<col; j++){
            if(board[i][j]==='R'){ // 찾았다
                Ri = i;
                Rj = j;
            }
        }
    }
    
    const dx = [0,1,0,-1], dy = [1,0,-1,0]; // 상하좌우 방향 배열
    const visit = Array(row).fill().map(()=>Array(col).fill(Number.MAX_VALUE)); // 2차원 배열 초기화
    
    const bfs = [];
    bfs.push([Ri,Rj,0]); // x,y,move값이다.
    visit[Ri][Rj] = 0;
    
    while(bfs.length>0){ // 큐가 비워질 때까지 한다.
        let [x, y, move] = bfs.shift();
        if(board[x][y] === 'G') return move; // bfs이므로 도착과 동시에 종료해주면 된다
        
        for(let d=0; d<4; d++){
            let nx = x, ny = y;
            
            while(true){ // 해당 방향의 제일 끝으로 이동하기
                nx += dx[d];
                ny += dy[d];
                if(nx<0 || ny<0 || nx>=row || ny>=col || board[nx][ny] === 'D'){
                    nx -= dx[d];
                    ny -= dy[d];
                    break;
                }
            }
            
            if(nx===x && ny===y) continue; // 제자리 이동은 안돼요~
            if(visit[nx][ny] <= value) continue; // 이전에 더 싸게 왔던 곳이면 패스
            
            visit[nx][ny] = move+1; // 이동거리 최신화
            bfs.push([nx,ny,move+1]); // 큐에 다음 좌표를 넣어준다
        }
    }
    
    // 모두 탐색했는데에도 목적지에 도달 못했기 때문에 -1을 리턴한다.
    return -1;
}

 

 

요즘 자바스크립트를 공부할 겸 코테언어로 사용하고 있는데 생각보다 괜찮은 것 같다.