62. Unique Paths | py풀이

1. 문제

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 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

m × n 격자(grid)가 있다.

 

로봇은 왼쪽 위 (0,0) 에서 시작해서

오른쪽 아래 (m-1, n-1) 까지 이동해야 한다.

 

단,

 

• 오른쪽 →
• 아래 ↓

이동 가능하다.

 

목적지까지 갈 수 있는 서로 다른 경로의 개수를 구하라.

2. 풀이

이 문제를 처음 보면 자연스럽게 이렇게 생각하게 된다.

 

현재 위치에서

• 위에서 왔거나
• 왼쪽에서 왔거나

 

즉 어떤 칸 (r, c)에 도착하는 경우의 수는(r-1, c)에서 오는 경우 + (r, c-1)에서 오는 경우

이걸 그대로 재귀로 표현하면 DFS가 된다.

 

dfs(r, c)

= dfs(r-1, c) + dfs(r, c-1)

 

시작점은 경로가 1. 

dfs(0,0) = 1

 

순수dfs로 풀면 시간초과가 나기때문에 메모이제이션으로 풀어야한다.

 

먼저, 이중리스트로 구현해보았다.

 

memo 배열 설계

memo = [[-1] * n for _ in range(m)]

memo[r][c] =
    -1 → 아직 계산 안됨
    값 → 해당 위치까지 오는 경로 수

 

# 이중리스트 구현

class Solution:
    def uniquePaths(self, m, n):

        # 메모 테이블 생성
        memo = [[-1] * n for _ in range(m)]

        def dfs(r, c):

            unique_paths = 0

            # base case (출발점)
            if r == 0 and c == 0:
                memo[r][c] = 1

            # 아직 계산 안된 경우만 계산
            if memo[r][c] == -1:

                # 위에서 내려오는 경우
                if r - 1 >= 0:
                    unique_paths += dfs(r - 1, c)

                # 왼쪽에서 오는 경우
                if c - 1 >= 0:
                    unique_paths += dfs(r, c - 1)

                memo[r][c] = unique_paths

            return memo[r][c]

        return dfs(m - 1, n - 1)

 

 

# 해시맵(딕셔너리) 구현

class Solution:
    def uniquePaths(self, m, n):

        memo = {}

        def dfs(r, c):

            # base case
            if r == 0 and c == 0:
                return 1

            # 이미 계산됨
            if (r, c) in memo:
                return memo[(r, c)]

            paths = 0

            if r > 0:
                paths += dfs(r - 1, c)

            if c > 0:
                paths += dfs(r, c - 1)

            memo[(r, c)] = paths
            return paths

        return dfs(m - 1, n - 1)

 

 

Bottom - up 방식으로도 구현해볼 수 있다.

 

아래, 오른쪽으로밖에 이동 못하기 때문에 가생이? 것들의 paths는 1일것으로 이것을 베이스케이스로 사용.

 

#이중리스트

class Solution:
    def uniquePaths(self, m, n):

        # DP 테이블 생성
        dp = [[0] * n for _ in range(m)]

        # 첫 행 = 1 (오른쪽만 이동 가능)
        for c in range(n):
            dp[0][c] = 1

        # 첫 열 = 1 (아래만 이동 가능)
        for r in range(m):
            dp[r][0] = 1

        # 점화식 채우기
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]

        return dp[m-1][n-1]

 

 

#해시맵(딕셔너리)

class Solution:
    def uniquePaths(self, m, n):

        dp = {}

        # 첫 행
        for c in range(n):
            dp[(0, c)] = 1

        # 첫 열
        for r in range(m):
            dp[(r, 0)] = 1

        # 점화식
        for r in range(1, m):
            for c in range(1, n):
                dp[(r, c)] = dp[(r-1, c)] + dp[(r, c-1)]

        return dp[(m-1, n-1)]