[프로그래머스] 등굣길

문제

• 집에서 학교까지 가는 길을 m x n 크기의 격자모양으로 나타낼 때 집은 (1, 1) 좌표에, 학교는 (m, n) 좌표에 있다.
• 물에 잠긴 지역의 좌표가 주어지고 이곳으로는 움직일 수 없다.
• 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지 리턴하기
• 1 <= m, n <= 100
• 1 <= 물에 잠긴 지역 <= 10

 

풀이

• 집이 (1, 1) 학교가 (m, n)에 위치해 있으므로 최단 경로는 항상 아래쪽과 오른쪽으로 이동하는 경우 밖에 없다.
• dp[a][b] : (a, b) 까지 갈 수 있는 최단 경로의 수
• 주의할 점은 puddles 좌표가 (y좌표, x좌표) 로 주어진다는 것.

def solution(m, n, puddles):
    puddles = set([tuple(pud) for pud in puddles])
    DIV = 1_000_000_007
    
    # dp[a][b] : (a, b)까지 갈 수 있는 최단 경로의 수
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[1][1] = 1
    
    for i in range(1, n+1) :
        for j in range(1, m+1) :
            if (j, i) not in puddles : 
                dp[i][j] += dp[i][j-1] % DIV + dp[i-1][j] % DIV

    return dp[n][m] % DIV

 

 

 

References

• 프로그래머스 고득점Kit DP