Unique Paths

# 코테 인프런 강의 https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC/dashboard

로봇이 m x n 격자 위에 있다 로봇의 처음 위치는 좌측 상단 모서리 grid[0][0] 에 위치해 있다 로봇은 우측 하단 모서리 grid[m-1][n-1]로 이동 하려 한다 로봇은 한번에 오른쪽이나 아래쪽으로만 움직일 수 있다.

 

두 정수 m과 n이 주어졌을 때, 로봇이 우측 하단 모서리에 도달할 수 있는 가능한 unique paths의 수를 반환하라

 

제약 조건 (1 <= m , n <= 100 )

 

테스트 케이스는 답이 2 * 10^9 이하가 되도록 생성

 

# 접근

 

완전 탐색으로 풀 수 있는가?를 판단하여 본다.

 

결국에는 m과n의 최댓값을 대입하였을 때,시간 복잡도를 고려하여 보자

 

생각 할 수 있는 경우 

 

1. 리턴 값의 범위가 매우 크기 때문에 완전 탐색을 시도 할 시 시간 초과가 날 가능성이 크다는 걸 짐작

2. 직접 수학 식을 도출 하여 최대한 계산하는 경우의 갯 수를 구하여 본다.

 

# 직접 수학 식 도출

 

DFS (묵시적 그래프) 를 이용하여  m - 1 번 오른쪽으로 n - 1 번 아래 쪽으로 가는 조합을 구한다.

 

수학식을 도출한 결과는

 

m+n-2 C m-1 이다.

 

이 식에 될 수 있는m과 n의 최댓값을 구하면 2 x 10^58 승 으로 매우 큰 숫자이다.

 

물론 직접적으로 계산하지 못하겠지만 완전 탐색으로 코드를 짜면 시간초과가 날 것이다.

 

 

# 완전탐색으로 코드 구현

 

테스트 케이스는 m = 3 , n = 7

output = 28

 

def dfs(r, c):
  if r == 2 and c == 6: # base 케이스, 끝 부분에 도달 하였을 때
    return 1

  unique_paths = 0

  if r + 1 < 3: # grid의 값이 넘어가지 않도록
    unique_paths += dfs(r+1,c)
  if c + 1 < 7:
    unique_paths += dfs(r,c+1)

  return unique_paths

 

위 코드에서 함수가 재귀적으로 호출 될 때 같은 계산과정을 거쳐 중복되는 계산이 있는지 확인해보자

 

 중복되는 계산 절차가 매우 많다 이 중복을 제거하여 시간효율성을 높여준다.

 

현재 계산해야 하는 결과값이 memo 딕셔너리에 존재하지 않는 경우 값을 저장해 주고

 

이미 값이 저장되어 있으면 그 값을 활용하게 한다.

def dfs(r, c):
  if r == 2 and c == 6: # base 케이스, 끝 부분에 도달 하였을 때
    return 1

  unique_paths = 0

  if r + 1 < 3: # grid의 값이 넘어가지 않도록
    unique_paths += dfs(r+1,c)
  if c + 1 < 7:
    unique_paths += dfs(r,c+1)

  return unique_paths

# 위 코드는 0,0 기준으로 짠 코드이다.

# 도착점을 기준으로 짠 dfs

memo = {}

def dfs(r,c):

  if r == 0 and c == 0:
    memo[(r,c)] = 1
    return memo[(r,c)]
  unique_paths = 0
  if (r, c) not in memo:
    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)]

 

memoization 방법은 여러가지 이다. 2중 리스트를 사용하여 저장할 수 있다.

 

 

# 최종 코드

def uniquePaths(m,n):
  memo = [[-1]* n for _ in range(m)]
  def dfs(r,c):
    if r == 0 and c == 0:
      memo[r][c] = 1
      return memo[r][c]
    
    unique_paths = 0
    
    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)

# 디버그를 통해 각 리스트에 반환된 값을 그림으로 확인

 

# bottom - up 방식으로 문제 풀이

 

왼쪽 위 가장자리는 항상 방법이 하나 뿐이므로 1로 미리 초기화

memo[1][1] 부터는 memo[0][1]값과 memo[1][0]값을 더한값 즉 관계식이 성립

 
memo[r][c] = memo[r-1][c] + memo[r][c-1]

 

# bottom up 코드 구현

def uniquePaths(m, n):
  memo = [[-1] * n for _ in range(m)]

  for r in range(m): # 왼쪽 위 가장자리 1로 초기화
    memo[r][0] = 1
  for c in range(n):
    memo[0][c] = 1

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

  return memo[m-1][n-1]

 

# 마지막으로 dp문제를 풀 때 생각해볼 것

 

top down , bottom up 방식 모두 생각해보면서 문제를 접근할 것

 

같은 코드를 반복학습하여 본인의 스킬로 체화 하기 (반복 학습 중요)