[Leetcode 아주 상세한 문제풀이] 62. Unique Paths – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 62번 문제 Unique paths 다.

우선 문제를 살펴보자.

 

리트코드 62번 문제 Unique paths 링크

Unique Paths - LeetCode

Unique Paths - LeetCode

 

 

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]). It 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

 

 

문제 설명

문제를 간략히 살펴보자. 가로 m 세로 n 크기를 가진 그리드 (grid[m-1][n-1])에서 움직이는 로봇이 있다. 이 로봇의 처음 시작 지점은 가장 위 왼쪽 코너다 (grid[0][0]). 우리는 이 로봇을 움직여 그리드에서 가장 아래 오른쪽 코너 (grid[m-1][n-1]) 까지 이동시키고자 한다. 단, 이때 로봇은 반드시 아래 혹은 오른쪽으로만 움직일 수 있다. 문제에서 요구하는 바는 주어진 m*n 그리드에서 가장 위 왼쪽 코너에서 시작해 가장 아래 오른쪽 코너까지 가는 경우의 수를 찾아내라는 것이다. 

문제 예시 2번을 보면 3*2의 그리드가 주어졌다. 즉, 세로는 3칸 가로는 2칸인 그리드다. 로봇이 가장 위 왼쪽 코너에서 시작해 가장 아래 오른쪽 코너로 가는 방법은 다음과 같은 3가지다.

 

i) 오른쪽->아래->아래

ii) 아래->아래->오른쪽

iii) 아래->오른쪽->아래

 

물론 그리드가 커질수록 경우의 수는 더 많아질 것이다. 때문에 문제에서 정답은 2*10^9 보다 같거나 작아야 한다고 명시해 두었다. 이제 문제를 한 번 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 dynamic programming을 이용할 것이다.

2D 배열을 만들어 각 cell에 도달할 수 있는 경우의 수를 그 cell에 표시할 것이다.

문제의 조건에 따라 로봇은 아래 혹은 오른쪽으로만 이동할 수 있다.

따라서 특정 cell에 도달할 수 있는 경우의 수는 i) 위쪽 cell에 도달할 수 있는 경우의 수와 ii) 왼쪽 cell에 도달할 수 있는 경우의 수의 합으로 표현할 수 있다.

좀 더 정확히는 다음과 같은 과정을 통해 접근할 수 있다.

해당 cell 까지 갈 수 있는 경우의 수를 나타내기 위한 2D array dp[i][j]를 만들어 준다.

이때 첫번째 행과 열은 1로 초기화를 시켜준다.

로봇은 아래 혹은 오른쪽으로만 움직일 수 있기 때문에 첫번째 행과 열은 경우의 수가 1가지 밖에 존재하지 않는다.

위에서 설명한대로 특정 cell에 도달할 수 있는 경우의 수 dp[i][j]는 다음과 같이 표현된다.

dp[i-1][j] (위쪽 cell에 도달할 수 있는 경우의 수) + dp[i][j-1] (왼쪽 cell에 도달할 수 있는 경우의 수)

따라서 이 과정을 통해 dp array의 모든 cell을 채우고 나면 우리가 찾고자 하는 가장 아래 오른쪽 코너까지 도달할 수 있는 경우의 수 dp[m-1][n-1]를 찾을 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

그리드 크기를 나타나는 값 m, n을 입력받기 위한 함수를 정의해 준다. (line 1)

앞서 설명한대로 특정 cell 까지 도달할 수 있는 경우의 수를 나타내기 위한 dp 배열을 만들어 준다. (line 4)

이때 dp 배열의 크기는 m*n이며 1로 초기화를 시켜준다.

이제 우리는 탐색을 시작할 것인데 (1, 1) 지점부터 탐색을 시작한다. (line 8-9)

위에서 설명한대로 첫번째 행과 열은 경우의 수가 1가지 밖에 없어 이미 1로 초기화가 되었기 때문이다.

그 후 dp 배열에서 현재 탐색하고 있는 cell에 도달할 수 있는 경우의 수를 업데이트 한다.

이때 업데이트는 탐색하고 있는 cell 위쪽 cell까지 도달할 수 있는 경우의 수와 왼쪽 cell까지 도달할 수 있는 경우의 수 합으로 나타낸다. (line 11)

이 모든 과정을 마치고 나면 dp 배열의 모든 cell이 업데이트 되었다.

따라서 우리가 구하고자 하는 그리드의 가장 아래 오른쪽 코너까지 도달할 수 있는 경우의 수 dp[m-1][n-1]을 리턴하고 종료한다. (line 14)

 

 

문제 풀이 코드

def uniquePaths(m, n):
    # Create a 2D array with all values initialized to 1
    # This is because there's exactly 1 way to reach any cell in the first row or first column
    dp = [[1] * n for _ in range(m)]
 
    # Iterate over the array starting from cell (1, 1)
    # since the first row and first column are already initialized
    for i in range(1, m):
        for j in range(1, n):
            # The number of ways to reach this cell is the sum of ways to reach the cell above and to the left
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
 
    # The bottom-right corner will have the total number of unique paths
    return dp[m - 1][n - 1]
 
# Example usage
print(uniquePaths(3, 7))  # Output: 28
print(uniquePaths(3, 2))  # Output: 3
 

 

 

관련 문제

리트코드 55번 Jump game 문제 풀이 링크

리트코드 70번 Climing stairs 문제 풀이 링크

리트코드 91번 Decode ways 문제 풀이 링크

리트코드 139번 Work break problem 문제 풀이 링크

리트코드 198번 House robber 문제 풀이 링크

리트코드 213번 House robber II 문제 풀이 링크

리트코드 300번 Longest increasing subsequence 문제 풀이 링크

리트코드 322번 Coin change 문제 풀이 링크

리트코드 1143번 Largest Common Subsequence 문제 풀이 링크

 

62. Unique Paths