[프로그래머스/Python] 등굣길 - Level3

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

코딩테스트 연습 - 등굣길

이 문제는 동적계획법 문제로 왼쪽 위 집에서부터 모든 경우의 수를 계산하며 학교까지 가면 되는 문제였다. 최단 경로로 가기 위해서는 오른쪽이나 아래쪽으로만 움직여야 하므로 [i][j] 위치에 오는 방법은 [i-1][j] 에서 오른쪽으로 움직이거나 [i][j-1] 에서 아래쪽으로 움직이는 방법이다. 따라서 경우의 수를 구할 때 오른쪽이나 아래쪽만 고려해주면 된다.

 

def solution(m, n, puddles):
    answer = [[0] * (m+1) for _ in range(n+1)]
    answer[1][1] = 1 # 시작점은 1로 만들어줌
    
    # 모든 경우의 수 계산
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1: continue # 시작점인 경우
                
            if [j,i] in puddles: # 물에 잠긴 지역인 경우
                answer[i][j] = 0
            else:
                answer[i][j] = answer[i-1][j] + answer[i][j-1]
                
    return answer[n][m] % 1000000007

answer 배열을 위치 좌표와 인덱스를 맞추기 위해 m+1, n+1 하였다. ( 위치가 (1,1) 부터 시작된다!) 시작점은 1로 만들어준 후 모든 경우의 수를 계산한다. 물에 잠긴 지역인 경우에는 접근할 수 없으므로 값을 0으로 만들어준다. 물에 잠긴 지역이 아닌 경우에는 오른쪽과 아래쪽으로 움직이는 경우의 수를 합쳐준다.