📖Problems
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 |
🔍Institution
먼저 웅덩이 문제는 중고등학생 때 최단경로에서 풀었던 기억이 있어, 유튜브 영상으로 최단경로 풀이법을 보았다.
20:15부터 내가 가물가물했던 부분을 설명해주셨다
직접 세는 방법!
🔍Approach
위의 영상을 토대로 직접 풀이해본다.
따라서, 아래와 같은 과정을 거칠 수 있다. 
이를 통해 규칙이 보인다. 점화식까지 세워볼 수 있을 것 같다.
수학 선생님께서 말씀하신 것처럼 경로를 풀면,
바로 위, 바로 왼쪽의 값과 더한 값을 저장한다.
새로 값을 넣을 칸 dp[i][j] = 바로 위쪽 칸 까지의 경로의 수 + 바로 왼쪽 칸 까지의 경로의 수
따라서, dp[i][j] = dp[i-1][j] + dp[i][j-1] 이다.
이때 1000000007로 나눈 나머지 값을 저장해야 하므로, 최종적으로는 dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007이 된다.
이때 문제에서의 행, 열에서 낚였다.. 문제에서 m, n이 주어졌고 m = 4, n = 3인 격자모양은
이렇게 나타내었고, 일반적으로 행 = 3, 열 = 4이기 때문에 격자가 반대로 되어 있음을 알 수 있다.
(행 = 3 → n, 열 = 4 → m)
따라서 주어진 웅덩이의 위치 puddles의 좌표 또한 반대로 되어 있다. 따라서 웅덩이의 위치도 i, j 좌표를 반대로 다시 저장해주어야 한다.
🚩My submission
Flow
puddles의 좌표를 미리 바꿔준다.dp를 0으로 초기화해주는데 미리 왼쪽, 위쪽을 한 줄씩 더 늘려서 초기화한다. (m+1, n+1)dp[1][1]은 집의 위치이므로 미리 1을 저장해준다.- 첫 for문은 행만큼 돌기 때문에
1~n+1까지 반복한다. 두 번째 for문은 열만큼 돌기 때문에1~m+1까지 반복한다.- 만약
dp[1][1]이라면, 그냥 넘어간다. [i, j]의 값이puddles의 값과 같다면, 웅덩이 부분은 지나지 않아야 하므로 0으로 처리한다.- 위 2가지의 경우가 아닐 때, 위에서 찾은 점화식을 넣어준다. (
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007)
- 만약
- 반복이 종료되면 가장 마지막 행, 마지막 열 (
dp[n][m])을 return한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(m, n, puddles):
puddles = [[q,p] for [p,q] in puddles]
dp = [[0] * (m + 1) for i in range(n + 1)]
dp[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
continue
elif [i, j] in puddles:
dp[i][j] = 0
else:
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
return dp[n][m]
🚩Others submission
프로그래머스에서 가장 좋아요를 많이 받은 코드
- 내 코드와 비슷하지만 조금 더 정갈한 느낌이 들어 가져왔다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(m,n,puddles):
grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
if puddles != [[]]: #물이 잠긴 지역이 0일 수 있음
for a, b in puddles:
grid[b][a] = -1 #미리 -1로 체크
grid[1][1] = 1
for j in range(1,n+1):
for k in range(1,m+1):
if j == k == 1: #(1,1)은 1로 만들어두고, 0이 되지 않도록
continue
if grid[j][k] == -1: #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
grid[j][k] = 0
continue
grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007 #[a,b] = [a-1,b] + [a,b-1] 공식
return grid[n][m]
💡TIL
- 처음엔 이걸 어떻게 풀지? 했는데, 방법을 찾아보며 수능 수학 선생님 강의를 보게 되었다. 어릴 적 수학, 최단경로에 대해 다시 복습할 수 있었다.