Leetcode 62. Unique Path(BFS, DP)

https://leetcode.com/problems/unique-paths/

Unique Paths - LeetCode

 

왼쪽 상단에서 우측하단까지 아래쪽과 오른쪽으로만 이동이 가능할 때,

고려할 수 있는 unique한 경로를 구하는 문제입니다

---

 

오랜만에 만난 matrix문제로 BFS로 풀이를 시작했습니다.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        matrix = [[-1 for i in range(n)] for j in range(m)]
        return self.path(matrix,0,0,m-1,n-1)
    
    def path(self,matrix,i,j,m,n):
        if i ==m and j==n:
            return 1
        
        if matrix[i][j] == -1:
            down, right = 0, 0
            if i < m:
                down = self.path(matrix,i+1,j,m,n)
            if j <n :
                right = self.path(matrix,i,j+1,m,n)
            matrix[i][j] = down + right
        return matrix[i][j]

경로의 수를 세는 문제이기 때문에 갯수를 누적합 시킬 수 있도록 지나가지 않은  matrix 는 -1로 기본 세팅을 합니다

그리고 m-1, n-1 최종 목적지에 도착하기 전까지는 열의 끝에 다다를때까지 오른쪽으로 이동하고, 아래쪽으로 이동하는

경우의 수를 각 셀에 저장합니다. 그리고 마지막에 matrix[m-1][n-1]의 경로수를 반환합니다.

 

---

 

하지만, 예상과 달리 이 문제는 수학적인 부분과 dynamic programming을 이용한 부분이 많았는데요

다른 분들의 풀이를 보면서 분석해보겠습니다.

 

BFS 풀이

def uniquePaths(self,m,n):
	paths = [[1]*n for _ in range(m)]
    
    q = deque()
    q.append((0,0))
    
    while q:
    	r,c = q.popleft()
        if r == m or c == n or paths[row][col]>1:
        	continue
        if row-1 >= 0 and col-1>=0:
        	paths[row][col] = paths[row-1][col] + paths[row][col-1]
            
        q.append((row+1,col))
        q.append((row,col+1))
     return paths[-1][-1]

 

path를 형성할 때 저처럼 2개의 for 문을 사용한게 아니라 1을 넣어서 계산을 단순화했습니다.

2번째 if 문에서 현재 셀의 경로는 곧 왼쪽과 위쪽의 경로 합과 같다는걸 명시적으로 보여준 풀이입니다

 

 

 

Dynamic Programming 풀이

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def up(m,n):
            if m==1 or n==1: return 1
            else: return up(m-1,n)+up(n-1, m)
        return up(m,n)

 

어떻게 보면 피보나치 수열 다이나믹 프로그래밍과 코드가 유사해보이는데요 처음 1행과 1열은 path가 1로 미리 세팅하고, 오히려 m과n에서 -1을 하면서 m행n열의 값을 계산하도록 했습니다.

 

@cache를 이용해서 계산 속도를 높인 것도 똑똑한 선택인 것 같습니다

 

 

 

✔ 수학법칙을 코드화한 풀이

 

이동하는 Path 의 경우의 수를 생각해봤을 때 아래처럼 지나가는 셀의 수는 행+수-겹치는셀2개 = m+n-2의 셀을 지납니다.

여기서 우리는 n-1 번만큼 오른쪽으로 이동할 수 있고, m-1한번만큼 내려갈 수 있습니다. 

Source: Leetcode

 

이 원리를 사용해서 아래코드는 전체 step을 이루는 경우의 수를 전체 n-1만큼 이동하는 경우의 수 * m-1만큼 이동하는

경우의 수로 나누어서 연산했습니다

 

def uniquePaths1(self, m, n):
    if not m or not n:
        return 0
    return math.factorial(m+n-2)/(math.factorial(n-1) * math.factorial(m-1))

 

 아래는 n개의 항목에서 k개 항목을 선택하는 방법의 수를 반환하는 math.comb를 사용해서 n+m-2의 셀을 n-1개를 어떤 식으로 뽑을 수 있을까?라는 문제로 바꾸어서 해석했습니다.(n-1을 알면 m-1을 자동으로 지정됩니다)

 

import math

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return math.comb(n + m - 2, n - 1)

 

 

 

↓↓ 이 문제를 애니메이션으로 잘 풀이한 유튜브 링크도 함께 공유드립니다 ↓↓ 

https://www.youtube.com/watch?v=fEcyKrdIkho