(python) 프로그래머 – 학교로 돌아가기

가장 먼저 생각할 것

1. mxn

좌표가 변경되었습니다

이……생각해보니……문제의 좌표가 모두 바뀌었다.

따라서 웅덩이의 좌표도 변경되었습니다.

예시가 (2, 2)인 것을 보면 그냥 때려달라고 한 문제인 것 같다.

주의 깊게 확인합시다. 왠지 Lv. 3이었다.

2. 최단거리

왼쪽 위에서 오른쪽 아래, 오른쪽, 아래로만 이동하기 때문에 항상 가장 짧은 거리가 나옵니다.

핵심은 최단 거리가 아니라 경로의 수임을 인식하십시오.

설명

def solution(m, n, puddles):
    # 오른쪽과 아래쪽으로만 움직이니까 모든 경로가 최단 경로
    # 즉, 최단 경로가 중요한게 아니라 그 타일까지 올 수 있는 경우의 수를 계산하는 것
    
    # 최단 경로의 개수 % 1000000007
    
    # D(i)(j) = D(i-1)(j) + D(i)(j-1)
    D = ((0 for _ in range(m + 1)) for _ in range(n + 1))
    D(1)(1) = 1
    
    puddles = set((tuple((p_r, p_c)) for p_c, p_r in puddles))
    
    #(1, 1) 제외, puddles 제외 하고 좌, 상 더해서 업데이트
    
    for i in range(1, n+1):
        for j in range(1, m + 1):
            if (i, j) == (1, 1) or (i, j) in puddles:
                continue
            
            D(i)(j) = D(i-1)(j) + D(i)(j-1)
        
    return D(n)(m) % 1000000007