Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 등굣길

[등굣길]

• 정신을 바짝 차려야하는(?) 행렬 경로 DP이다.
• 문제의 설명은,
  • 1-indexed이며
  • 좌표는 $(x, y)$의 형태로 설명한다. (해당 좌표에 접근 시 $dp[y][x]$로 접근해야 한다.)

Solution 1. $O(nm)$

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

• $dp[i][j]$를 집(시작점)에서 $[i][j]$(문제의 좌표 표현에 따르면 $(j, i)$)까지 도달할 수 있는 최단경로의 개수라 하자.
• dp table을 0으로 초기화한다. 이 때, 크기는 $(m+1)\times(n+1)$으로 만든다.
  • 이렇게 테두리를 둘러놓음으로써 1-indexed의 puddles 처리도 깔끔해지고,
  • 어떤 물에 잠긴 지역이 첫 번째 행이나 첫 번째 열에 위치하더라도 따로 처리해줄 필요가 없다.
• 물에 잠긴 지역을 1로 마킹해 놓는다.
• dp table을 순회하며 $dp[i][j]$가 1인 경우 (물에 잠긴 지역인 경우) 도달할 수 없는 곳이라고 볼 수 있으므로 0을 할당하고,
• 1이 아닌 경우 최단경로를 갱신한다.

Solution 2. $O(nm)$

def solution(m, n, puddles):
    dp = [[1]*m for _ in range(n)]
    
    zero_i, zero_j = 101, 101
    for x, y in puddles:
        dp[y-1][x-1] = 0
        if x == 1: zero_i = min(zero_i, y)
        if y == 1: zero_j = min(zero_j, x)
    
    if zero_i < 101:
        for i in range(zero_i, n):
            dp[i][0] = 0
    
    if zero_j < 101:
        for j in range(zero_j, m):
            dp[0][j] = 0
    
    for i in range(1, n):
        for j in range(1, m):
            if dp[i][j]: dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % 1000000007
            
    return dp[-1][-1]

• $dp[i][j]$를 집(시작점)에서 $[i][j]$(문제의 좌표 표현에 따르면 $(j, i)$)까지 도달할 수 있는 최단경로의 개수라 하자.
• dp table을 1로 초기화한다. 이 때, 크기는 $m \times n$으로 만든다.
• 이 때, 물에 잠긴 지역이 첫 번째 행 또는 첫 번째 열에 위치한 경우를 생각해 보자.
  • $4 \times 3$ 크기의 격자에서, $(3, 1)$ ($=dp[0][2]$)에 물에 잠긴 지역이 존재한다고 하자. 그렇다면 오른쪽과 아래쪽만으로만 움직여 집에서 학교까지 갈 때, $dp[0][3]$에는 도달할 수 없다. (그 값이 $0$이어야 한다.)
  • 하지만 1로 초기화했으므로, $dp$에 물에 잠긴 지역을 마킹하면서 이 지역이 첫 번째 행이나 첫 번째 열에 위치한 경우 그 위치를 마킹해 놓고, 그 뒤에 오는 지역에 대해 모두 0으로 바꿔주어야 한다.
• Solution 1. 에 비해 메모리는 조금이나마 덜 사용하지만, 최악의 경우 물에 잠긴 지역이 $(1, 1)$에 위치할 때 $O(n+m)$의 시간이 추가로 소요되며, 물에 잠긴 구역을 마킹할 때에도 if문과 min() 갱신에 추가적인 시간이 소요된다.

---