문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

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

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  - m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

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

입출력 예 설명

접근 방법

이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 문제에서 최단거리의 갯수를 구하라고 하여 다익스트라도 생각을 해보았지만, 이 문제에서 주어진 갈 수 있는 방향이 오른쪽과 아래밖에 없다는 것은 다른 곳으로 돌아서 갈 수 없다는 뜻이기도 하기 때문에 항상 최단거리로 도달할 수 밖에 없다는 것을 깨달았다. 그래서 다이나믹 프로그래밍으로 접근하였다.

우선 1, 1 즉 출발점을 기준으로 dp[1][i]와 dp[i][1]을 모두 1로 갱신해야 한다. 이때 주의할 점은 dp[1][i]와 dp[i][1]을 갱신하던 중에 물웅덩이를 만날 경우 그 뒤에 존재하는 dp[1][i]와 dp[i][1]는 갱신하지 않고 0으로 두어야 한다는 것이다. 이 위치에 물 웅덩이가 존재할 경우 그 뒤에로는 접근할 수 없기 때문이다.

점화식을 구하기 위해 도식화해보았고, 점화식은 다음과 같이 구할 수 있었다.
dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%1,000,000,007

초기 dp갱신이 끝나면 2, 2부터 n, m까지 순회하며 dp[i][j]에 dp[i-1][j]와 dp[i][j-1]을 더하여 dp[i][j]를 갱신해준다. 갱신이 끝나면 dp[m][n]을 정답으로 하여 반환한다.

이 문제의 경우 물웅덩이의 좌표에 대한 정보가 제대로 입력되지 않아 삽질을 조금 했다. m, n이 x축, y축으로 입력 받아졌기 때문에 당연히 물웅덩이도 x축, y축 순서로 입력받아질 것이라고 생각했지만, 물웅덩이는 y축, x축으로 입력받아졌다. 문제에서 제대로 표기되지 않아 발생한 문제였다^^..

• dp 리스트를 0으로 (n+1)*(m+1)을 채운다.
• 1부터 m까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 [i, 1]가 puddles에 존재할 경우, 반복문을 탈출한다.
  -> dp[1][i]를 1로 갱신한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 [1, i]가 puddles에 존재할 경우, 반복문을 탈출한다.
  -> dp[i][1]을 1로 갱신한다.
• 2부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 2부터 m까지 반복하는 j에 대한 for문을 돌린다.
  --> 만약 [j, i]가 puddles에 존재할 경우, 다음 반복으로 넘어간다.
  --> 그 외에는 dp[i][j]에 (dp[i-1][j]+dp[i][j-1])%1,000,000,007을 더한다.
• answer에 dp[n][m]%1,000,000,007을 저장한다.
• answer를 반환한다.

solution.py

def solution(m, n, puddles):
    dp=[[0]*(m+1) for _ in range(n+1)]
    for i in range(1, m+1):
        if [i, 1] in puddles:
            break
        dp[1][i]=1
    for i in range(1, n+1):
        if [1, i] in puddles:
            break
        dp[i][1]=1
    for i in range(2, n+1):
        for j in range(2, m+1):
            if [j, i] in puddles:
                continue
            else:
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%1000000007
    answer=dp[n][m]%1000000007
    return answer