[프로그래머스] 등굣길

문제

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.제한사항

 

 

입출력

 

입력 예)

4 3 [[2, 2]] 

출력 예)

4

 

입출력 예 설명

 

 

 

 

 

내 생각

 

문제 요약

1. 격자의 크기 m, n 그리고 웅덩이가 있는 곳 좌표가 주어진다.

2. (1,1)은 집, (m,n)은 학교가 위치하고, 오른쪽과 아래쪽으로만 움직인다. 

3. 최단경로 개수 구하기 (%1,000,000,007)

 

 

집 (0, 0)

학교 (m, n)

puddels 피해서 오른쪽, 아래쪽 움직여서 최단경로 개수 구하는 문제로 dp 문제이다!

그러니까 (i,j)에 도달할 수 있는 경로의 개수는 왼쪽(i-1,j)과 위쪽(i,j-1)에서 올 수 있는 위치를 구해야 한다.

 

점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

dp 테이블 초기화하고, 웅덩이 있는 곳은 표시해주어야 한다. (이 때, 좌표 거꾸로 ! 주의!)

그리고 경로를 찾으면서 웅덩이라면 다음 계산을 위해 0으로 바꿔준다. (웅덩이가 있는 위치는 이동할 수 없음) 그리고 뛰어넘기!

 

아래처럼 표시하면 대각선 합을 본다고 생각하면 편하다!

 

집  1  1  1

1  -1  1  2

1   1  2  4

 

내 코드

def solution(m, n, puddles):
    dp = [[0] * (m+1) for i in range(n+1)] #dp 초기화
    dp[1][1] = 1  #시작위치(집)
    
    #웅덩이 위치라면? dp = -1 로 
    for i, j in puddles:
        dp[j][i] = -1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            #웅덩이(dp = -1)라면? continue 
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            #웅덩이가 아니라면? 현재 칸 = 왼쪽 칸 + 윗 칸
            dp[i][j] += (dp[i-1][j] + dp[i][j-1]) % 1000000007
    return dp[n][m]