[자료구조] 등굣길 파이썬 (DP)

def solution(m, n, puddles):
    dp = [[0]*(m+1) for _ in range(n+1)]
    # first row and colum are 1
    for i in range(n+1):
        for j in range(m+1):
            
            if i == 1 or j == 1:                
                dp[i][j] = 1
            if i == 0 or j == 0:
                
                dp[i][j] = 0
    
    if m <= 1 and n <= 1:
        return dp[m][n]
    else:
        for i in range(2,n+1):
            for j in range(2,m+1):
                # print(dp[i][j],i,j)
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
                for p in puddles:

                    if i == p[0] and j == p[1]:
                        dp[i][j] = 0
                        # print(i,j)
                
    return dp[-1][-1]

이런식으로

 

left dp + up dp의 합이 curr dp로 하는 건 분명한데

 

예제는 통과하는데 test case에서 하나만 맞고 틀리다는 것.

 

아마 dp 초기 설정에서 첫 행 모두 1, 첫 열 모두 1 설정하는 부분에서 틀리지 않나 싶다.

 

내일 일어나서 다시 풀어보자.

---

 

def solution(m, n, puddles):
    map = [[0] * (m + 1) for _ in range(n + 1)]
    map[1][1] = 1 # 1, 1 좌표의 경우의 수는 1입니다

    for x, y in puddles:
        map[y][x] = -1 # 웅덩이 좌표 값을 -1로 바꿉니다.

    for y in range(1, n + 1):
        for x in range(1, m + 1):
            if map[y][x] == -1: # 웅덩이는 생략합니다.
                map[y][x] = 0 # 이후 합에 영향이 안가도록 0으로 바꿉니다
                continue

            # 왼쪽과 위의 경우의 수를 합칩니다.
            map[y][x] += (map[y][x - 1] + map[y - 1][x]) % 1000000007

    return map[n][m] # n, m 좌표의 경우의 수를 리턴합니다.

웅덩이를 체크하는 부분에서

map을 traverse하면서 하는 것이 아니라

미리 사전에 -1로 체크해놓고

traverse 진행하다가 만나면 0으로 초기화 하는 것이 핵심