[LeetCode] Unique Paths, Unique Paths II (javascript)

Unique Path

전형적인 최단경로 찾기 조합 문제!

 

(m + n)! / m! * n! 식을 이용하여 풀었다.

 

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // (m+n-2)! / ((m-1)! * (n-1)!)
    console.log(factorial(m+n-2), factorial(m-1), factorial(n-1))
    return factorial(m+n-2)/(factorial(m-1)*factorial(n-1));
};

const factorial = (n) => {
    if(n == 0) return 1;
    let num = n;
    for (let i = num - 1; i > 1; i--){
        num *= i;
    }
    return num;
}

 

---

Unique Path II

 

다만 팩토리얼 공식으로 푸는 경우.. 경로에 장애물이 있으면 문제가 복잡해지는데 

그게 바로 Unique Paths II 문제다.

 

처음엔 여집합을 활용해 아래와 같이 풀어보려 했다.

장애물 없을 때의 경로수 - (출발점~장애물 경로수 * 장애물~도착점 경로수)

한참을 풀다.. 장애물이 하나만 있지 않다는 것을 나중에 깨달았다.

 

그래서 결국 어릴때 풀던대로, 칸마다 1, 1, 2, 3, ... 이렇게 써주며 더해가는 방식으로 구현했다.

참고 : https://bhsmath.tistory.com/154 중 "초등학교 방법"(...)

 

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  let grid = [];
  for (let i = 0; i < obstacleGrid.length; i++) {
    grid.push(obstacleGrid[i].map((g) => (g === 0 ? 0 : -1)));
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (i === 0 && j === 0 && grid[0][0] !== -1) {
        grid[0][0] = 1;
        continue;
      }
      if (grid[i][j] === -1) continue;

      // 좌 상을 더한다.
      const left = j > 0 ? minusSafe(grid[i][j - 1]) : 0;
      const up = i > 0 ? minusSafe(grid[i - 1][j]) : 0;
      grid[i][j] = left + up;
    }
  }

  return minusSafe(grid[grid.length - 1][grid[0].length - 1]);
};

const minusSafe = (num) => (num < 0 ? 0 : num);

 

 

문제 링크

Unique Path : https://leetcode.com/problems/unique-paths/

Unique Path II : https://leetcode.com/problems/unique-paths-ii/