[Python] 등굣길

1. 문제

 

 

2. 풀이 과정

방법 1) 필요한 부분만 보고 count

def solution(m, n, puddles):
    answer = 0
    arr = [[0]*(m) for _ in range(n)]
    
    #웅덩이는 -1로 표기
    if puddles != [[]]:
        for x, y in puddles:
            arr[y-1][x-1] = -1
    
    q = set() #중복 제거
    q.add((0, 0))
    arr[0][0] = 1
    while q:
        temp = set()
        for a, b in q:
            if a == n-1 and b == m-1:
                return arr[a][b]%1000000007
            #하
            na = a + 1
            if na < n and arr[na][b] != -1:
                arr[na][b] += arr[a][b]
                temp.add((na, b))
            #우
            nb = b + 1
            if nb < m and arr[a][nb] != -1:
                arr[a][nb] += arr[a][b]
                temp.add((a, nb))
        q = temp
    
    return answer%1000000007

 

방법 2) 전체를 차례대로 돌면서 count, 더 효율적인 코드

def solution(m, n, puddles):
    arr = [[0]*(m) for _ in range(n)]
    
    if puddles != [[]]:
        for x, y in puddles:
            arr[y-1][x-1] = -1
            
    for i in range(n):
        for j in range(m):
            if i==j==0 :
                arr[i][j] = 1 #시작
            elif arr[i][j] == -1: #웅덩이면 0으로 처리 => 다음 칸들의 더하기에 영향X
                arr[i][j] = 0
            else:
                #위에서 더하기
                if i > 0:
                    arr[i][j] += arr[i-1][j]
                #왼쪽에서 더하기
                if j > 0:
                    arr[i][j] += arr[i][j-1]

    return arr[n-1][m-1]%1000000007