[LeetCode]Unique Paths

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 그리드에서 가장 오른쪽 아래로 가는 Unique 경로의 수를 구하는 문제입니다.

 

처음 시도한 답안 - 실패, DFS 이용

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        answer = set()

        def dfs(i , j, path):
            if i > m or j > n:
                return

            if i == m-1 and j == n-1:
                answer.add(path)
                return

            dfs(i+1, j, path+'down')
            dfs(i, j+1, path+'right')

        dfs(0, 0, '')

        return len(answer)

접근 방법

1. 처음에 시도했던 방법입니다. 그리드를 DFS 알고리즘으로 순회합니다.
2. dfs 내부에서
   1. (0, 0) 지점부터 시작해서 내부에서 오른쪽과 아래로 재귀 호출을 진행합니다.
   2. 그리드를 벗어나면 리턴합니다.
   3. 오른쪽 아래 지점에 도착했다면 도착한 경로를 추가합니다.
3. dfs 순회후 방문한 지점들의 set의 개수를 구합니다.

해당 방법으로 갯수는 맞출 수 있었으나 Time Limit Exceeded에 걸리게 되었습니다. 그리드가 켜지는 경우에는 dfs 호출이 너무 많아지기 때문에 시간 복잡도를 초과하게 되었던 것 같습니다.

DP를 이용한 방법으로 다시 시도하였습니다.

 

두번째로 시도한 답안 - DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path_count = [[1]* n for _ in range(m)]

        for row_idx in range(1, m):
            for col_idx in range(1, n):
                path_count[row_idx][col_idx] = path_count[row_idx-1][col_idx] + path_count[row_idx][col_idx-1]

        return path_count[-1][-1]

접근 방법

1. DP를 활용한 방법으로 풀이합니다.
2. DP로 활용할 path_count 이차원 리스트를 할당합니다.
3. 그리드를 이중 포문으로 한 지점씩 순회하면서
   1. 현재 지점은, 현재 등장한 지점 바로 위 + 현재 등장한 지점 바로 왼쪽의 값을 더한 값으로 설정합니다.
4. 가장 마지막 지점에 누적된 값이 Unique한 경로의 누적합이 됩니다.

각 지점에서의 유니크한 경로를 구하다보면 일정한 규칙이 발견되고 그로 인해서 DP로 풀이할 수 있는 문제입니다.

(i, j) 지점에서의 유니크한 경로는 (i-1, j) + (i, j-1)의 값으로 구할 수 있습니다.

 

아래 그림을 통해 path_count DP가 어떻게 변하는지 확인할 수 있습니다.

1	1	1	1	1	1	1
1	2	3	4	5	6	7
1	3	6	10	15	21	28