[프로그래머스] 등굣길(Python)

프로그래머스 - 등굣길

풀이

1. graph[i][j] = graph[i - 1][j] + graph[i][j - 1] 의 반복으로 구할 수 있음

2. 인덱스 오류 방지 위해 (n + 1) * (m + 1) 크기의 그래프를 만들어줌

3. 시작점(1, 1)은 1로 저장, 나머지는 0, 웅덩이는 -1

4. 1번 코드를 반복 후 graph[n][m] 값 을 반환

코드

def solution(m, n, puddles):
    graph = [[0 for i in range(m + 1)] for j in range(n + 1)]
    graph[1][1] = 1
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if [j, i] not in puddles:
                a = graph[i - 1][j]
                b = graph[i][j - 1]
                graph[i][j] += a if a > 0 else 0
                graph[i][j] += b if b > 0 else 0
    return graph[n][m] % 1000000007