[Javascript/PGS] Lv.3 : 경주로 건설 (BFS)

 

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

프로그래머스

---

프로그래머스 레벨 3.

BFS + 삼차원 배열...

ㅋㅋㅋㅋㅋ하 ㅠㅠ 이차원배열로 풀다가 삽질하느라 1시간 걸림

카카오 기출이라 그런지, 구현하면서 신경써야 할 내용이 정말정말 많았다.

삼차원배열 bfs에서 방향에 따라 최솟값을 저장해줘야 하는데,

출발점에서는 방향이 상관없기 때문에 이것도 분기처리를 해줘야 했음!!

그리고 코너에서는 코너 도로 + 직진도로 모두 필요하기 때문에, 600을 더해줘야 한다.

 

개인적으로 함정이 많았던 문제라고 생각

실력 증진하기 참 어렵다

다시 느낀 점이지만, JS는 배열 초기화가 참 불편하다..^-^

 

나의 풀이

let dx = [0,1,0,-1]; // 시계방향 : 위, 오른쪽, 아래, 왼쪽
let dy = [1,0,-1,0];
let visited;
let Board;

function canVisit(x, y, size){
    if(x<0 || x>=size || y<0 || y>=size) return false;
    if(Board[x][y]==1) return false;
    return true;
}

function solution(board) {
    Board = board;
    let answer;
    let size = board.length;
    // 방향에 따른 저장이 추가로 필요하므로, 삼차원 배열 활용
    let visit = Array.from({length:size},()=>
                           Array.from({length:size},()=>
                                      Array(4).fill(Infinity)));
    visited = visit;
    let q = [];
    q.push([0,0,-1,0]); // x, y, 방향, 금액
    while(q.length){
        let [x, y, d, cost] = q.shift();
        for(let i=0; i<4; ++i){
            let nx = x + dx[i];
            let ny = y + dy[i];
            if(canVisit(nx,ny,size)){
                // 직선  100원, 코너 500원+100원 추가
                let newCost = d==i? cost+100 : cost+600;
                if(d<0) newCost = cost+100; // 출발할때(방향 : -1) 항상 직진임
                if(visited[nx][ny][i]>newCost){
                    q.push([nx,ny,i,newCost]);
                    visited[nx][ny][i] = newCost;
                }
            }
        }
    }
    // console.log(visited);
    answer = Math.min(...visited[size-1][size-1]);
    return answer;
}