[LeetCode 풀이/python] 62. Unique Paths (medium)

문제 설명: 로봇이 m x n 형태 격자의 왼쪽 상단 (아래 그림에서 'Start' 표시된 곳) 에 위치해 있다. 이 로봇은 한 번에 아래 혹은 오른쪽 방향으로 한 칸 씩만 움직일 수 있다. 로봇이 격자의 오른쪽 하단 (아래 그림에서 'Finish' 표시된 곳) 에 도달하고자 할 때, 고유한 경로는 얼마나 존재하는가?

 

(A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?)

 

예시 1)

입력: m = 3, n = 7  -->  출력: 28

 

예시 2)

입력: m = 3, n = 2  -->  출력: 3

설명: 좌상단에서 우하단으로 가는 경로는 다음과 같이 3가지 존재함: ▶ -> ▼ -> ▼  /  ▼ -> ▼ -> ▶  /  ▼ -> ▶ -> ▼ 

 

예시 3)

입력: m = 7, n = 3  -->  출력: 28

 

예시 4)

입력: m = 3, n = 3  -->  출력: 6

 

제한 조건:

• 1 <= m, n <= 100
• 정답 개수는 최대 2 * 10^9 와 같거나 작은 것이 보장됨

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • m x n 형태 격자의 (1, 1) 위치에서 (m, n) 위치로 이동하는 고유한 경로 수는 ((m-1)+(n-1))! / (m-1)! (n-1)! 을 계산하여 쉽게 구할 수 있음
  • (m-1) 개의 ▶ 와 (n-1) 개의 ▼ 를 일렬로 나열하는 조합 수를 계산하는 것과 같음

 

• 코드 구현

import math
def uniquePaths(m: int, n: int) -> int:
    return int(math.factorial(m+n-2) / (math.factorial(m-1) * math.factorial(n-1)))

 

• 결과
  • O(1) 의 시간 복잡도로 해결... (이런 식으로 구조화된 수식으로 표현 가능한 문제가 좋아..)

 

 

 

[풀이 2안]

• 접근법
  • 경로 중간에 장애물(obstacles) 이 있는 UniquePaths II 문제를 풀면서, 해당 문제도 다른 식의 풀이가 어떻게 가능한지 찾아보다가 DP 를 이용한 풀이로도 구현해 봄
  • 1 <= i <= m , 1 <= j <= n 일 때 (i, j) 까지 도달하는 경로는 (i-1, j) 에서 오른쪽으로 or (i, j-1) 에서 아래로 한 칸 이동하는 것 뿐!  -->  dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

• 코드 구현

def uniquePaths(m, n):
    dp = [ [0]*(n+1) for _ in range(m+1) ]
    dp[1][1] = 1
    for i in range(1, m+1):
        for j in range(1, n+1):
            if (i == 1) and (j == 1) : continue
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

 

• 결과
  • Classic DP solution in Python...
  • O(m*n) 이지만 m, n 이 큰 수가 아니라 무난히 통과...!