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

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

❗풀이방법

1. 고등학교 때 길 찾기 문제랑 똑같이 접근
2. 1행과 1열을 dp에서 1로 지정
3. 하지만 중간에 그래프에서 0이 나오는 경우, 해당 인덱스부터 끝까지는 dp에서 0으로 처리(이동 불가)
4. 상, 좌 dp값을 합쳐서 현재값을 업데이트
5. [행-1][열-1]이 정답

 

❗코드

def solution(m, n, puddles):
    graph = [[1 for _ in range(m)] for _ in range(n)]
    dp = [[0 for _ in range(m)] for _ in range(n)]

    for i, j in puddles:
        graph[j - 1][i - 1] = 0


    row_idx = m
    col_idx = n

    for i, g in enumerate(graph[0]):
        if g == 0:
            row_idx = i
            break
    for i, g in enumerate([g[0] for g in graph]):
        if g == 0:
            col_idx = i
            break


    for i in range(row_idx):
        dp[0][i] = 1
    for i in range(col_idx):
        dp[i][0] = 1


    for i in range(1, n):
        for j in range(1, m):
            if graph[i][j] == 1:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    
    
    return dp[n-1][m-1]