[DP] 프로그래머스 “등굣길” Python 풀이

문제 링크

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

풀이

• 대표적인 경로 찾기 알고리즘입니다.
• 2차원 DP 테이블을 생성한 뒤,
• 시작 위치는 1로, 웅덩이의 위치는 -1로 변환합니다.
• 이후, DP 테이블의 칸들을 순서대로 탐색해 나갑니다.
  • 현재 칸이 웅덩이(-1)일 경우엔, 0으로 변환합니다.
  • 현재 칸이 웅덩이가 아닐 경우엔, 왼쪽 칸과 위쪽 칸의 합으로 변환합니다.
• 세부 알고리즘은 아래 코드와 같습니다.

코드

def solution(m, n, puddles):

    # 2차원 DP 테이블 초기화
    dp = [[0] * (m+1) for _ in range(n+1)]

    # 시작 위치는 1로 처리
    dp[1][1] = 1

    # 웅덩이는 -1로 처리
    for i, j in puddles:
        dp[j][i] = -1

    for i in range(1, n+1):
        for j in range(1, m+1):
            # 시작 위치는 건너뛰기
            if (i == 1 and j == 1):
                continue
            # 현재 위치가 웅덩이라면
            if (dp[i][j] == -1):
                dp[i][j] = 0
            # 현재 위치가 웅덩이가 아니라면
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j]

    return dp[n][m] % 1000000007