[JavaScript] 프로그래머스 경주로 건설 LEVEL3

문제출처

const [dx, dy] = [[0, 0, -1, 1], [-1, 1, 0, 0]]; // 상 하 좌 우

const bfs = (board) => {
    const n = board.length;
    const visit = Array.from(Array(n), () => new Array(n).fill(0));
    const queue = [[0, 0, 0, 0]]; // x, y, 현재까지 비용, 방향(상하: 0, 좌우: 1)
    
    while (queue.length) {
        const [x, y, cost, dir] = queue.shift();
        
        for (let i=0; i<4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || board[nx][ny] === 1) continue;
            
            const direction = i < 2 ? 0 : 1;
            const costByDirection = dir === direction || (x === 0 && y === 0) ? 100 : 600;
            
            if (visit[nx][ny] === 0 || visit[nx][ny] >= cost + costByDirection) {
                visit[nx][ny] = cost + costByDirection;
                queue.push([nx, ny, cost + costByDirection, direction]);
            }
        }
    }
    
    return visit[n-1][n-1];
};

function solution(board) {
    return bfs(board);
}

풀이

흔한 BFS 문제와 약간 차이가 존재한다.

1. 상-하 방향으로 이동하고 있었는지, 좌-우 방향으로 이동하고 있었는지를 구분해 비용을 다르게 계산해야 한다.
2. visit 배열을 검사할 때, 단순히 방문한 노드는 건너뛰는 것이 아니라 이전에 계산했던 비용이 현재 계산된 비용보다 크다면 다시 queue에 집어넣는다.