LeetCode 62. Unique Paths 자바 문제 풀이

문제

Unique Paths - LeetCode

문제 해결 방법

• 문제 해결방법에는 조합을 사용하는 방법과 동적프로그래밍을 사용하는 방법등이 있습니다.
• 조합을 사용하면 수학적으로 계산하므로, 코드는 인간이 이해하기 쉽지만, 팩토리얼 계산떄문에 시간이 오래걸릴수 있고, 동적프로그래밍은 추가적인 배열을 사용해야 해서 공간을 좀더 사용한다는 특징이 있습니다.

조합을 이용하는 방법

• 오른쪽과 왼쪽으로 이동해야 하는 양은 변함이 없습니다.
• 조합이란, 일부 문자를 선택하여 만들 수 있는 모든 가능한 경우의 수이며, n과 r을 선택할수 있으면 쉽게 구현할수 있습니다.
  • n: 전체 요소의 수
  • r: 선택해야 하는 요소의 수
  • 계산식: Total combinations = n! / (r! * (n - r)!)
• 문제에서 입력받는 grid의 열과 행을 i과 j이라고 가정해봅시다.
• 오른쪽의 요소의 수는 i-1이라고 볼수 있으며, 오른쪽 요소의 수는 j-1이라 볼수 있습니다.
• 그러므로, 전체요소의 수는 i-1+j-1=i+j-2 입니다.이를 n이라고 할수 있습니다.
• 선택해야 하는 요소의 수는 행 혹은 열입니다. 어느쪽을 하든 상관이 없으므로, 더 작은 쪽을 고릅니다. 그래서 r은 (i-1) 혹은 (j-1) 입니다.
• 계산식에 대입하는 코드를 작성합니다.

동적 프로그래밍을 사용하는 방법

• 동적프로그래밍으로 계산하는 방법은 기본적으로 모든 경우의 수를 계산하며 다음 배열로 넘어가는 방법입니다.
• 모든 경우의 수를 저장할 2d 어레이, result를 선언합니다.
• 첫 번째 열의 모든 셀과 첫 번째 행의 모든 셀의 값은 1입니다. 문제에서 시작점은 반드시 가장 왼쪽, 위쪽입니다. 왜냐하면 첫 번째 열의 셀은 오른쪽으로만 이동하여 도달할 수 있고, 첫 번째 행의 셀은 아래쪽으로만 이동하여 도달할 수 있기 때문입니다.
• 나머지 셀들에 대해 result[i][j]의 값을 계산합니다. 이는 result[i-1][j] (위쪽 셀의 경로 수)와 result[i][j-1] (왼쪽 셀의 경로 수)를 더한 값과 동일합니다. 이는 오른쪽으로 이동하는 경우와 아래쪽으로 이동하는 경우의 경로 수를 합한 것입니다.

| j=0 | j=1 | j=2
-------------------
i=0 |  1  |  1  |  1
i=1 |  1  |  2  |  3
i=2 |  1  |  3  |  6

• 마지막 셀인 dp[m-1][n-1]에는 도착 셀까지의 고유한 경로 수가 저장됩니다. 이 값을 반환합니다.

결론

위 문제는 동적프로그래밍으로 해결하는것이 이상적입니다. 중복계산을 피할수 있기떄문에 수학적 계산보다 빠르며, 작은 하위문제로 나눌수 있기때문에 더더욱 빠르게 실행이 가능하기 떄문입니다.

Github Link

https://github.com/eunhanlee/LeetCode_62_UniquePaths_Solution.git

Combination 시간복잡도: O(nCr), 공간복잡도: O(1)

class Solution {
    /**
     * m x n 그리드에서 시작 셀 (1, 1)에서 도착 셀 (m, n)까지의 고유한 경로 수를 조합을 사용하여 계산한다.
     *
     * @param m 그리드의 행 수
     * @param n 그리드의 열 수
     * @return 시작 셀에서 도착 셀까지의 고유한 경로 수
     */
    public int uniquePaths(int m, int n) {
        int mathN = m + n - 2; // 선택할 수 있는 총 요소 수 (m+n-2)
        int mathR = (m > n) ? n - 1 : m - 1; // 선택해야 하는 요소 수 (m-1 또는 n-1 중 작은 값)

        long result = 1; // 큰 수를 다루기 위해 long 자료형 사용

        // 조합 공식 (nCr)을 사용하여 결과 계산
        for (int i = 1; i <= mathR; i++) {
            result = result * (mathN - mathR + i) / i;
        }

        return (int) result;
    }
}

Dynamic programming 시간복잡도: O(mn), 공간복잡도: O(mn)

class Solution2 {
    /**
     * 주어진 m x n 그리드에서 시작 셀 (1, 1)에서 도착 셀 (m, n)까지 이동하는 고유한 경로의 수를 계산한다.
     *
     * @param m 그리드의 행 수
     * @param n 그리드의 열 수
     * @return 시작 셀에서 도착 셀까지의 고유한 경로의 수
     */
    public int uniquePaths(int m, int n) {
        int[][] result = new int[m][n];

        // 첫 번째 열의 모든 셀 초기화
        for (int i = 0; i < m; i++) {
            result[i][0] = 1;
        }

        // 첫 번째 행의 모든 셀 초기화
        Arrays.fill(result[0], 1);

        // 나머지 셀의 경로 수 계산
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                result[i][j] = result[i - 1][j] + result[i][j - 1];
            }
        }

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