등굣길 (python)

프로그래머스 문제 - 등굣길 LV3

https://programmers.co.kr/learn/courses/30/lessons/42898?language=python3

👀 깃헙 소스

문제설명

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

입출력 예

m	n	puddles	     return
4	3	[[2, 2]]	4

솔루션
중고등학교 때 경로구하기 방법 사용
ex)

코드

def solution(m, n, puddles):
    puddles = set([(y-1, x-1) for x, y in puddles])
    dist = [[0] * (m) for _ in range(n)]

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

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

팁
i가 0이거나 j가0인 맨 왼쪽과 오른쪽을 따로 생각하지 않아도 되는것이
i-1과 j-1이 범위밖이어도 -1을 가리키고 있기 때문에 맨 마지막 줄을 바라보게 됨. 이때 0으로 초기화되어있어 더하는데 아무 상관이 없음. 따로 예외처리 해주지 않아도 된다.