[프로그래머스] 경주로 건설 / JavaScript / Level 3

🚩문제 주소

📄풀이

그래프 탐색 -> BFS, DP

마지막 25번 테스트케이스가 너무 안풀려서 프로그래머스 질문하기 탭에서 도움을 받아서 작성했습니다. https://school.programmers.co.kr/questions/40589

방향에 따라서 비용이 달라지기 때문에 2차원 DP 배열을 사용하여 계산할 경우 특정 좌표까지 최소비용이라도 다음좌표에서도 방향이 여러 가지기 때문에 항상 최소비용을 보장할 수 없기 때문입니다.

👨‍💻코드

function solution(board) {
  const N = board.length;
  const visited = Array(N)
    .fill()
    .map(() =>
      Array(N)
        .fill()
        .map(() => Array(4).fill(Infinity))
    ); // 3차원 dp
  const DIRECTIONS = [
    [1, 0],
    [-1, 0],
    [0, -1],
    [0, 1],
  ]; // 우,좌,상,하

  const isValid = (x, y) => x >= 0 && x < N && y >= 0 && y < N && board[x][y] !== 1; 
  // 유효한지 체크
  const q = [
    [0, 0, 0, 0],
    [0, 0, 0, 3],
  ]; // 오른쪽, 아래쪽 출발
  while (q.length) {
    const [x, y, cost, dir] = q.shift();
    for (let i = 0; i < DIRECTIONS.length; i++) {
      const nx = x + DIRECTIONS[i][0];
      const ny = y + DIRECTIONS[i][1];

      if (isValid(nx, ny)) {
        let new_cost = cost + 100; // 직선도로는 100원
        if (dir !== i) new_cost += 500;
        // dir과 i가 같지 않다는 것은 방향이 달라졌다는 뜻이므로 500원 추가 (곡선도로 600원)
        if (new_cost < visited[nx][ny][i]) {
          visited[nx][ny][i] = new_cost;
          q.push([nx, ny, new_cost, i]);
        }
      }
    }
  }

  return Math.min(...visited[N - 1][N - 1]);
}