[프로그래머스 lev3/JS] 경주로 건설

문제 출처

프로그래머스 lev3 - 경주로 건설

나의 풀이

1차시도(52/100, 시간초과)

단순히 dfs로 풀었으나 시간초과가 발생한다

function solution(board) {
  let w = board.length  
  let h = board[0].length 
  let ch = Array.from({length: h}, () => new Array(w).fill(false))
  let dir = [[-1,0], [1,0], [0,1], [0,-1]]
  let answer = Number.MAX_SAFE_INTEGER
  
  function dfs(sum, b, a, prevDir, tmp){
    if(b === w-1 && a === h-1){
      answer = Math.min(answer, sum)
      console.log(tmp, sum)
    }
    
    dir.forEach(([y,x], idx) => {
      let dy = b + y 
      let dx = a + x 
      
      if(dy>=0 && dy<=h-1 && dx>=0 && dx<=w-1 && ch[dy][dx] === false && board[dy][dx] === 0){
        ch[dy][dx] = true 
        let currDir = idx<=1 ? 'vtc' : 'hrz'
        
        if(currDir !== prevDir){
          prevDir==='' 
            ? dfs(sum+100, dy, dx, currDir, [...tmp, [dy,dx,100]])
            : dfs(sum+600, dy, dx, currDir, [...tmp, [dy,dx,500]])
        }
        else if(currDir === prevDir){
          dfs(sum+100, dy, dx, currDir, [...tmp, [dy,dx,100]])
        }

        ch[dy][dx] = false 
      }
    })
  }
  ch[0][0]=true 
  dfs(0, 0, 0, '', [[0,0,0]])
  return answer 
}

2차시도(92/100)

dp 배열을 추가했다.
재귀를 돌면서 dp에 값을 계속 최소값으로 업데이트하는 동시에 현재 재귀의 sum이 dp[b][a] 보다 크면 return을 해서 불필요한 탐색을 줄이려 했다.

function solution(board) {
  let answer = Number.MAX_SAFE_INTEGER

  let w = board.length  
  let h = board[0].length 
  let ch = Array.from({length: h}, () => new Array(w).fill(false))
  let dir = [[-1,0], [1,0], [0,1], [0,-1]]
  let dp = Array.from({length: h}, () => new Array(w).fill(Number.MAX_SAFE_INTEGER))
  
  function dfs(sum, b, a, prevDir){
    dp[b][a] = Math.min(dp[b][a], sum)
    if(dp[b][a] < sum) return 

    if(b === w-1 && a === h-1){
      answer = Math.min(answer, sum)
    }
    
    dir.forEach(([y,x], idx) => {
      let dy = b + y 
      let dx = a + x 
      
      if(dy>=0 && dy<=h-1 && dx>=0 && dx<=w-1 && ch[dy][dx] === false && board[dy][dx] === 0){
        ch[dy][dx] = true 
        let currDir = idx<=1 ? 'vtc' : 'hrz'
        
        if(currDir !== prevDir){
          prevDir==='' 
            ? dfs(sum+100, dy, dx, currDir)
            : dfs(sum+600, dy, dx, currDir)
        }
        else if(currDir === prevDir){
          dfs(sum+100, dy, dx, currDir)
        }

        ch[dy][dx] = false 
      }
    })
  }
  ch[0][0] = true 
  dfs(0, 0, 0, '')
  return answer 
}

다른 풀이 bfs+dp

방향에 따라서 비용이 달라지는 걸 전혀 생각하지 못했다.

어떤 방향인지에 따라,
특정 좌표까지는 최소 비용이 아니더라도 최종적으로는 최소 비용이 될 수 있기 때문에, 무조건 당장 최소 비용이 아니라고 해서 return을 해버리면 궁극적인 최소 비용을 구할 수 없다.

즉, 특정 좌표까지의 최소 비용이 다음좌표의 최소비용을 무조건 보장하지 못한다. 어떤 방향은 중간에는 최소 비용이 아니더라도 마지막에는 최소 비용이 될 수 있다는 점이다.

이 때문에 dp를 3차원 배열을 사용해야 한다.
dp[y좌표][x좌표][4방향에 대응하는 index값]

function solution(board) {
  const N = board.length;
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  const q = [
    [0, 0, 0, 0],
    [0, 0, 1, 0],
  ];

  const dp = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => Array(dirs.length).fill(Infinity))
  );

  const isInBoard = (x, y) => x >= 0 && x < N && y >= 0 && y < N && board[x][y] !== 1;

  while (q.length) {
    const [x, y, pDirI, cost] = q.shift();

    dirs.forEach(([dx, dy], nDirI) => {
      const [nx, ny] = [x + dx, y + dy];
      if (!isInBoard(nx, ny)) return;

      const newCost = cost + (pDirI === nDirI ? 100 : 600);

      if (newCost < dp[nx][ny][nDirI]) {
        dp[nx][ny][nDirI] = newCost;
        q.push([nx, ny, nDirI, newCost]);
      }
    });
  }
  return Math.min(...dp[N - 1][N - 1]);
}

참고

[JS][프로그래머스] 경주로 건설 / 정답, 해설
JS풀이 (테케25번까지 통과)
[C++로 풀이] 경주로 건설 (DFS, BFS, 다익스트라)⭐⭐⭐