프로그래머스 - [Level 3] 경주로 건설(JAVASCRIPT)

프로그래머스 경주로 건설[2020 카카오 인턴십]

카테고리 : 다익스트라

 다익스트라 알고리즘을 활용하면 간단하게 풀린다.
 
우선, 블록은 경주로 건설 비용을 기록하는 배열이라고 정의하자.
풀이 과정은 아래와 같다.

(0,0)을 출발점으로 잡고 bfs 탐색을한다.

1) queue에 [y위치, x위치, 이전 방향, 이전 비용] 형식으로 저장한다.

2) 비용은 이전 방향과 현재 이동하는 방향이 같다면
즉, 직선이라면 현재 비용= 이전 비용 + 100 원,
그 반대라면(코너포함) 현재 비용= 이전 비용 + 600 원으로 계산한다.

3) 현재 이동하고자 하는 곳이 벽이라면 무시해준다.

4) 현재 이동하고자 하는 블록을 아직 지나치지 않았다면
경주로를 건설하고, 블록에 현재 비용을 기록해주고, queue에 넣어준다.

이미 지나친 블록일 경우에는 블록 비용>=현재 비용 일 경우에만
queue에 넣어준다.

같은 지점을 경유할 경우, 이미 건설된 경주로 비용보다 크다면
절대 최소값이 될 수 없다.

한 가지 주의할 점은
비용은 각 경우의 수마다 관리해줘야한다.
블록[N-1][N-1]을 return 하면 예외가 발생한다.

소스 코드

function solution(board) {
    let answer = 987654321;
    const dy=[1,0,-1,0];
    const dx=[0,1,0,-1];
    const len=board.length;
    const arr=Array.from(Array(board.length),()=>Array(board.length).fill(0));
    const queue=[];
    
    const bfs=()=>{
        queue.push([0,0,1,0]);
        queue.push([0,0,0,0]);
        while(queue.length){
            let now=queue.shift();
            let y=now[0],x=now[1],dir=now[2],cost=now[3];
            if(y===len-1 && x===len-1) answer=(answer>cost)?cost:answer;
            for(let i=0;i<4;i++){
                let ny=y+dy[i],nx=x+dx[i];
                if(ny<0 || nx<0 || ny>len-1 || nx>len-1 || board[ny][nx]) continue;
                let charge=(dir===i)?cost+100:cost+600;
                if(!arr[ny][nx] || arr[ny][nx]>=charge){
                  arr[ny][nx]=charge;  
                  queue.push([ny,nx,i,charge]);
                } 
            }
        }
    }
    
    bfs();
    return answer;
}