Python으로 푸는 LeetCode 62. Unique Paths (Medium)

(0,0)에서 (n,m)까지 도달하는 모든 경우의 수를 구하는 프로그램을 짜시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기 

github에서 코드 보기

문제 풀이

BFS로 문제를 풀 경우에는 Time Limit Exceeded(시간 초과) 에러가 난다.

BFS로 풀기

BFS로 푸는 방법도 설명해보자면, (0,0)부터 시작하여 오른쪽, 아래 부분으로 이동가능한 경우에 pos_list라는 array(파이썬에서는 List)에 다음으로 체크할 위치 정보를 넣어준다. 다음으로 체크할 지점에 +1을 해준다. while문을 돌때마다 pos_list에 들어있는 지점들을 하나씩 pop() 해서 꺼내준다.  또다시 오른쪽, 아래부분의 지점이 범위를 초과하지 않은 유효한 범위인지 확인하며 위와 같은 작업을 pos_list가 모두 빌때까지 반복해준다. 이렇게 되면 field에는 pos_list를 거쳐서 다음 위치까지 이동가능한 경우의 수가 기록되어 있다. 맨 마지막에 filed[n-1][m-1] 지점에 있는 수를 반환해주면 끝.

Dynamic Programming으로 풀기

DP는 중간 값을 저장하고 저장한 값을 활용하여 빠르게 결과를 도출해 내는 것이다. m=7, n=3인 경우를 예를 들어보면 아래와 같다.

LeetCode 62. Unique Paths (그림으로 보기)

위와 같이, 위, 왼쪽에 놓여진 값들을 합하면 현재의 위치로 도달할 수 있는 경로의 수가 나온다. 주의할 점은 r과 c의 index가 0인 경우에는 1가지의 경우에 수밖에 존재하지 않는다는 예외를 처리해줘야 한다. 이러한 예외가 발생하기 되는 이유는 이동 방향이 오른쪽과 아래 방향이라는 점이 조건으로 명시되어 있기 때문이다. 이 방법을 사용하면 문제를 무난하게 통과할 수 있다.

파이썬 코드 - BFS

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        Time Limit Exceeded
        """
        r = n
        c = m
        field = [[0]*c for i in range(r)]
        rd = [0, 1]
        cd = [1, 0]
        pos_list = [(0,0)]
        while pos_list:
            pos = pos_list.pop()
            pr, pc = pos
            field[pr][pc] += 1
            for i in range(2):
                temp_r = pr + rd[i]
                temp_c = pc + cd[i]
                if temp_r < 0 or temp_c < 0 or r <= temp_r or c <= temp_c:
                    continue
                pos_list.append((temp_r, temp_c))
        return field[r-1][c-1]

파이썬 코드 - DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        Runtime : faster than 40.64% of Python3
        Memory Usage : less than 5.25% of Python3
        """
        r = n
        c = m
        field = [[0]*(c) for i in range(r)]
        direction = [(0,-1), (-1, 0)]
 
        for i in range(r):
            for j in range(c):
                if i == 0 or j == 0:
                    field[i][j] = 1
                    continue
 
                for next_pos in direction:
                    add_r, add_c = next_pos
                    temp_r = i + add_r
                    temp_c = j + add_c
                    if temp_r < 0 or temp_c < 0 or r <= temp_r or c <= temp_c:
                        continue
                    field[i][j] += field[temp_r][temp_c]
        return field[r-1][c-1]