[CodeKata] 프로그래머스 : 7.10(토), 경주로 건설

 

🧮  풀이

DFS로 초기 접근했으나, 최단경로를 구해야하므로 BFS로 변환해서 구현해보다가 모범답안 풀이를 하게 되었다.

 

🖇 리뷰

모든 노드에 이동하는 최소 건설비용을 저장하는 BFS + 다익스트라 알고리즘 을 활용했다.

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;
}

* 출처 : https://gwang920.github.io/algorithm/progreammers-2-67259/

1. answer는 건설비용(정답)을 저장하는 변수, dx와 dy는 각각 이동방향(동서남북)을 의미한다고 보면 된다.
2. len은 board의 길이(도착여부, 초과여부 확인하기 위함), arr은 board의 각 노드(미로칸)에 건설비용을 저장하는 2차원 배열이다.
3. queue는 BFS를 위해 다음 이동할 노드(미로칸)을 저장하는 큐 자료형태이다. 
4. queue에 [0,0,1,0], [0,0,0,0] 을 넣어준다. 각각은 y, x, dir(이동방향, dx&dy의 인덱스), cost(건설비용) 이다.
5. 먼저, x와 y가 모두 len-1(도착지점)에 도달하면 answer를 현재 answer과 cost 중 최소값으로 최신화해준다.
6. 그렇지 않다면, dx & dy를 순회하며 ny, nx로 옮겨준다. 이 때, charge(현재 건설비용)은 i와 dir이 같은지 여부에 따라 100과 600 중 선택되는 것이다.
7. arr[ny][nx]가 false(0)이라면 방문하지 않은 것이고, 혹은 현재 charge보다 클 경우 더 작은 값으로 최신화할 수 있다. 그렇기에 arr[ny][nx]를 charge 값으로 할당(혹은 최신화) 해주며, queue에 해당정보를 넣어준다.

 

레벨이 높기 때문에 단순한 DFS, BFS로만 풀 수 있는 문제들이 출제되지 않는다.

특히, 최소비용으로 최신화하는 다익스트라나 플로이드-와샬 등의 알고리즘에 대해 복기하면서 다음 문제부턴 직접 구현해보고자 노력해야겠다.