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

📍문제

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

 

📍풀이

- DP를 활용해 이차원 배열을 북서에서 남동 방향으로 채워나간다

- 장애물이 있는 공간은 경로 숫자를 0으로 만듬

- 이차원 배열의 0행, 0열을 1로 초기화 할 때, 장애물이 등장한다면 쭉 0으로 만들면 됨

📍코드

def solution(m, n, puddles):
    board = [[0] * m for _ in range(n)]
    puddle_set = {(x - 1, y - 1) for y, x in puddles}

    if (0, 0) in puddle_set:
        return 0

    board[0][0] = 1

    for i in range(1, m):
        if (0, i) in puddle_set:
            board[0][i] = 0
        else:
            board[0][i] = board[0][i - 1]

    for i in range(1, n):
        if (i, 0) in puddle_set:
            board[i][0] = 0
        else:
            board[i][0] = board[i - 1][0]

    for i in range(1, n):
        for j in range(1, m):
            if (i, j) in puddle_set:
                board[i][j] = 0
            else:
                board[i][j] = board[i - 1][j] + board[i][j - 1]

    return (board[n - 1][m - 1]) % (10 ** 9 + 7)


print(solution(4, 3, [[2, 2]])) # 4