[프로그래머스 Lv.3] 등굣길 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

풀이

최단거리만 세면 되기에, 특정 칸에 진입할 수 있는 방법은 왼쪽 또는 위쪽으로 한정된다. 그렇기에 현재 칸에 도달할 수 있는 방법의 수는 현재의 왼쪽에 위치한 칸까지 도달할 수 있는 방법의 수와 현재의 위쪽에 위치한 칸까지 도달할 수 있는 방법의 수를 더한 값이다.

결론적으로 이전 값을 기반으로 하여 현재 값을 갱신해나가는 풀이가 진행되기에 DP로 이 문제를 풀이할 수 있다.

def solution(m, n, puddles):
    arr = [[0 for _ in range(m)] for _ in range(n)]

    def check(i, j): # 체크 대상 칸이 도달할 수 있는 칸인지 체크하는 함수
        is_i_valid = 0 <= i < n # 도달할 수 있는 열인지
        is_j_valid = 0 <= j < m # 도달할 수 있는 행인지
        is_not_puddle = arr[i][j] != -1 # 물에 잠긴 칸이 아닌지
        return is_i_valid and is_j_valid and is_not_puddle # 도달할 수 있는지 여부를 반환
        
    
    arr[0][0] = 1 # 시작하는 칸에 도달할 수 있는 방법은 한가지
    for x, y in puddles: arr[y-1][x-1] = -1 # 물에 잠긴 칸을 표시
        
    for i in range(n):
        for j in range(m):
            if arr[i][j] != 0: continue # 해당 칸의 값이 0이 아니라면 이미 체크한 곳임
            if check(i, j-1): arr[i][j] += arr[i][j-1] # 현재 위치의 왼쪽 칸이 도달할 수 있는 곳이라면 방법의 수를 업데이트
            if check(i-1, j): arr[i][j] += arr[i-1][j] # 현재 위치의 윗쪽 칸이 도달할 수 있는 곳이라면 방법의 수를 업데이트
    
    return arr[n-1][m-1] % 1000000007 # 최종 위치에 도달할 수 있는 벙법의 수 반환