[프로그래머스] 등굣길 (level3, python)

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

---

입출력 예

---

입출력 예 설명

 

---

풀이 코드

def solution(m, n, puddles):
    answer = 0
    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1
    
    for p in puddles:
        a, b = p
        dp[b-1][a-1] = -1
    
    for i in range(n):
        for j in range(m):
            if dp[i][j] == 0:
                if i-1 == -1 or (i-1 >= 0 and dp[i-1][j] == -1):
                    # 위가 벽이거나, 벽은 아닌데 웅덩이인 경우
                    if j-1 == -1 or (j-1 >= 0 and dp[i][j-1] == -1):
                        continue
                    else:
                        dp[i][j] = dp[i][j-1]
                elif j-1 == -1 or (j-1 >= 0 and dp[i][j-1] == -1):
                    # 왼쪽이 벽이거나, 벽은 아닌데 웅덩이인 경우
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
                    
    return dp[-1][-1] % 1_000_000_007

전형적인 다이나믹 프로그래밍 문제이다.

 

문제에서 주의깊게 보아야 할 특성은, (1, 1) 위치에 무조건 집이 있고 (m, n) 위치에 무조건 학교가 있다.

이동을 한다면 오른쪽으로 이동하거나, 아래로 이동하는 경우밖에 없다.

따라서 한 칸에 대해서 직전의 이동을 고려할 때에는 위에서 내려왔는지, 왼쪽에서 오른쪽으로 왔는지를 고려하면 된다.

 

 

이 그림을 보면 이해가 편하다.

+ 표시가 된 칸은, 왼쪽에서 이동하거나, 위에서 이동할 수 있는 경우이다.

따라서 dp 배열을 만들어 메모이제이션을 해가며 로직을 완성하면 된다.

 

추가로 코드에 나온 주석을 보면, 어떻게 생각을 했는지 이해하기 편할 것이다.