[프로그래머스] 동적계획법(Dynamic Programming) - 등굣길 (Python 풀이)

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

 

 

 

정수 삼각형 문제와 비슷한 동적계획법 문제이다.

[프로그래머스] 동적계획법(Dynamic Programming) - 정수 삼각형 (Python / Swift 풀이)

동적계획법 문제에서는 중간 단계의 결과값을 임시로 저장할 공간을 만들어주어야 한다.

m은 가로길이, n은 세로길이이므로 n*m 크기의 저장공간 storage 을 만들어준다.

storage = [[0 for i in range(m)] for j in range(n)]

 

(i,j) 좌표까지의 최단경로의 개수를 구하는 함수를 만든다.

여기서 주의해야 할 점이 i와 j의 범위가 다음과 같다는 것이다.

0 < i <= n

0 < j <= m

따라서 n*m 크기의 저장공간에 (i,j) 좌표까지의 최단경로의 개수 결과값을 담기 위해서는 storage[i-1][j-1] 을 이용해야 한다.

 

• (i, j) 좌표까지 최단경로 = (i-1, j) 좌표까지 최단경로 + (i, j-1) 좌표까지 최단경로
• 출발지라면 1 반환
• 물에 잠긴 좌표라면 지나갈 수 없으므로 0반환
  • 여기서 주의해야 할 것은 입력 좌표값과 배열 좌표값이 가로세로가 바뀌어있다는 것이다.
  • puddles에 있는 값이 [a, b]라면, storage에서는 [b-1][a-1]을 찾아야 한다.

 

마지막으로 결과값은 1000000007로 나눈 나머지를 반환한다.

def solution(m, n, puddles):
    storage = [[0 for i in range(m)] for j in range(n)]
    
    def shortPath(i, j):
        
        # 물에 잠긴 곳
        if [j, i] in puddles:
            storage[i-1][j-1] = 0
            return 0
        
        if storage[i-1][j-1] != 0:
            return storage[i-1][j-1]
        
        # 출발지일 경우
        if (i-1, j-1) == (0, 0):
            storage[i-1][j-1] = 1
            return 1
        
        # 위에서 올 수 있음
        if i > 1:
            storage[i-1][j-1] = storage[i-1][j-1] + shortPath(i-1, j)
            
        # 왼쪽에서 올 수 있음
        if j > 1:
            storage[i-1][j-1] = storage[i-1][j-1] + shortPath(i, j-1)
        
        return storage[i-1][j-1]
    
    return shortPath(n,m) % 1000000007