LeetCode Unique Paths (JavaScript)

링크 : https://leetcode.com/problems/unique-paths/description/

문제 설명

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

---

문제 풀이

1. (시간 초과) BFS를 활용하여 문제 풀이 -> 0,0 부터 오른쪽, 아래 가능한 경로를 stack에 쌓으면서 최종 목적지 까지 가는 횟수를 카운트

-> 2가지의 경우의 수가 존재하고 m x n 행을 전부 탐색해야 하므로 O(2^(m+n))의 시간복잡도를 가짐

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const move = [[1, 0], [0, 1]];
    let answer = 0;

    const stack = [[0, 0]];

    while (stack.length > 0) {
        let [x, y] = stack.pop();

        if ((x === n - 1) && (y === m - 1)) {
            answer++;
            continue;
        }

        for (let i = 0; i < move.length; i++) {
            const mx = x + move[i][0];
            const my = y + move[i][1];

            if (mx < n && my < m) {
                stack.push([mx, my]);
            }
        }
    }

    return answer;
};

2. 2차원 배열을 한번만 순회하여 정답을 구하는 방법으로 O(m + n)으로 해결

각 위치는 현재 위치까지 도달할 수 있는 갯수를 의미. 즉, 아래, 오른쪽으로 이동이 가능하므로

현재 위치(x, y)기준 왼쪽(x - 1, y), 위(x, y - 1)의 값을 더한 값이 현재 위치의 도달 가능 횟수임.

최종적으로 (m - 1, n - 1)을 리턴해주면 됨.

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let arr = Array.from({length: m}, () => Array.from({length: n}, () => 1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
        }
    }

    return arr[m - 1][n - 1];
};

---

결론

BFS를 이용해 쉽게 해결할 순 있지만 시간복잡도 초과 문제가 발생하고,

문제를 좀 더 생각해보면 각 위치가 어떠한 방식으로 생성이 될 수 있는지 파악할 수 있다.