[LeetCode] Unique Paths

문제링크

 

m*n 행렬이 주어질때 로봇은 [0][0]에서 출발해서 [m-1][n-1]로 도착하려한다.
이때 로봇이 도착지에 갈 수 있는 방법의 수를 구하여라

조건 : 로봇은 오른쪽과 아래로만 이동할 수 있다.

접근 방법

1. Dynamic Programming 방법으로 풀이

2. 재귀함수 방식으로 풀이


1. DP로 풀이를 하기 위해서는 규칙을 발견해야한다.

규칙은 그림으로 보면 더 쉬운데

이전 행과 이전 열의 값을 더하면 다음 행열의 값이 나온다.

즉, dp[row][col] = dp[row-1][col] + dp[row][col-1]

2차 행렬을 다루므로 2중 for문이 필요하다.

const dp = Array.from({length : m}, () => Array(n).fill(1));
    
for(let row = 1; row < m; row++){
    for(let col = 1; col < n; col++){
        dp[row][col] = dp[row-1][col] + dp[row][col-1];
    }
}​

dp[0][0] ~ dp[m][0] === 1
dp[0][0] ~ dp[0][n] === 1
이므로 2차원 배열을 생성할때 1로 채워준다.

그리고 2중 for문을 통해 규칙에 맞춰 값을 넣어준다.


2. 재귀함수

재귀함수 역시 규칙과 종료 조건을 찾아야한다.

종료 조건은 아래와 같이 구했다.

if(row > m || col > n){
    return 0;
}else if(row === m && col === n){
    return 1;
}

row와 col이 범위를 벗어나면 0으로 종료하고, 목적지에 도착하면 1을 반환한다.


반복은 아래와 같이 하나의 목적지로 가능 경로를 구할때까지 반복한다.

return re(row+1, col) + re(row, col+1);

하지만 재귀함수로는 m = 23, n = 12 처럼 큰 범위를 구하진 못했다.

개발자 도구에서는 시간 제한이 없기때문에 dp와 같은 값을 구할 수 있었지만 leetcode에서는 실패하였다.

 

 

// DP 방법
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
 var uniquePaths = function(m, n) {
    const dp = Array.from({length : m}, () => Array(n).fill(1));
    
    for(let row = 1; row < m; row++){
        for(let col = 1; col < n; col++){
            dp[row][col] = dp[row-1][col] + dp[row][col-1];
        }
    }
    
    return dp[m-1][n-1];
}

 

// 재귀 방법
var uniquePaths = function(m, n) {
    
    const re = (row, col) => {
        if(row > m || col > n){
            return 0;
        }else if(row === m && col === n){
            return 1;
        }
        
        return re(row+1, col) + re(row, col+1);
    }
    
    return re(1, 1)
};