프로그래머스(programmers) 등굣길 python 정답[동적계획법 풀이]

프로그래머스(programmers) 등굣길 python 정답[동적계획법 풀이]

문제 링크

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

문제 정답

def solution(m, n, puddles):
    # n x m 격자
    puddles = [[q,p] for [p,q] in puddles]      # 미리 puddles 좌표 거꾸로
    dp = [[0] * (m + 1) for i in range(n + 1)]  # dp 초기화
    dp[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 [i, j] in puddles:    # 웅덩이 위치의 경우 값을 0으로
                dp[i][j] = 0
            else:                    # 현재 칸은 왼쪽 칸, 위 칸의 합산!
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    return dp[n][m]

문제 해설

이 문제는 아무도 이의를 제기하는것 같지 않지만, 사실 m x n 격자가 아니라 n x m 격자다

즉 문제 관점에서 y와 x에 관련된 정보가 바뀌어 있기 때문에 이를 감안하고 풀어야한다.

(puddle의 y,x 좌표 반전, 구하는 것은 dp[n][m])

지도

Puddle이 있는 곳을 이동거리 0으로 표시하면서 다이나믹 프로그래밍을 적용하면 되는 간단한 문제이다.

주의할 점은 i와 j는 1부터 시작하지만, i-1,j-1를 계산해야 하므로 0으로 패딩을 준다는 것이다.

이런 문제는 거의 다 이러한 트릭이 존재하므로 알아두면 좋다

[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 0, 1, 2]
[0, 1, 1, 2, 4]