[programmers] 프로그래머스 등굣길

문제

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

프로그래머스

풀이

• 지도의 위, 아래를 더하면서 경우의 수를 구할 것이라서 윗줄 왼쪽줄이 한줄씩 더 필요함
• m+1, n+1 배열생성
• 웅덩이는 -1로 초기화
• 웅덩이를 지날때는 0으로 다시 초기화 -> 추후 계산에 영향을 끼치지 않기 위함
• 위,왼쪽 배열을 더하면서 마지막 도착지의 결과값 반환
• 초반에는 웅덩이를 셋팅하지 않고 반복문에서 같은 것을 발견해줄 경우 제거하는 형식으로 진행하였으나 실패

코드

#등굣길
# 일부 지역 물에 잠김
# 오른쪽, 아래쪽만 움직임
def solution(m, n, puddles):
    #지도 생성 위, 아래를 더하면서 진행할것이라서 윗줄 옆줄 초기값 0 셋팅
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

    #웅덩이 셋팅
    for deleteX, deleteY in puddles:
        dp[deleteY][deleteX] = -1

    #시작점 셋팅
    dp[1][1] = 1


    for y in range(1,n+1):
        for x in range(1, m+1):
            if dp[y][x] == -1:
                dp[y][x] = 0
                continue
            # if puddles:
                # if y == puddles[0][0] and x == puddles[0][1]:
                    # del puddles[0]
                    # continue
            dp[y][x] += dp[y-1][x] + dp[y][x-1]

    return dp[n][m] % 1000000007