[JS] 경주로 건설

문제

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

프로그래머스

 

풀이

이번 문제는 최소 비용을로 각 노드를 연결해야 하는 문제이다.

 

BFS 알고리즘을 이용해 인접한 노드를 방문하고 끝 지점까지 연결해야 하며 각 노드까지 연결되는데에 필요한 비용을 DP알고리즘을 이용해 저장한다.(시간 복잡도와 노드와 노드를 연결할 시 비용을 계산)

 

하지만, 이 문제에서는 한가지 트릭을 추가적으로 생각해야한다. 바로 한 노드로 들어오는 방향까지 생각해야한다. 이유는 커브길을 만들 경우 추가적으로 500원이 더 들기 때문이다. 즉 이 문제에서는 방향성이라는 하나의 변수가 존재 하는 것이다.

 

이러한 트릭은 DP에 저장되는 노드 데이터를 들어오는 방향별로 저장하면된다.(문제에서는 4방향으로 들어오니 4개의 비용을 각각 저장)

 

코드

function solution(board) {
  const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const dp = Array.from({ length: board.length }, () => Array.from({ length: board[0].length }, () => Array.from({ length: 4 }, () => Infinity)));
  const que = [[0, 0, 1, 0], [0, 0, 3, 0]];
    
  while (que.length > 0) {
    const [cy, cx, d, cost] = que.shift();
        
    for (let i = 0; i < 4; i++) {
      const [ny, nx] = [cy + dir[i][0], cx + dir[i][1]];
            
      if (ny >= 0 && ny < board.length && nx >= 0 && nx < board[0].length && board[ny][nx] !== 1) {
        const newCost = cost + (i === d ? 100 : 600);
        if (newCost < dp[ny][nx][i]) {
          dp[ny][nx][i] = newCost;
          que.push([ny, nx, i, newCost]);
        }
      }
    }
  }
    
  return Math.min(...dp[board.length - 1][board[0].length - 1]);
}