문제
m*n 격자의 1,1은 집, m,n은 학교이다.
일부 지역이 물에 잠겼을 때, 잠기지 않은 지역을 통해 학교에 가려한다.
최단경로의 개수를 1,000,000,007로 나눈 나머지를 반환하라.
입출력 예시
| m | n | puddles | result |
|---|---|---|---|
| 4 | 3 | [[2,2]] | 4 |
접근
이건 고등학교 때 배운 것 같다.
위에서 아래로, 왼쪽에서 오른쪽으로 한칸씩 탐색하며 현재 칸까지 올 수 있는 경우의 수는 다음과 같다.
1
d[x][y] = d[x-1][y] + d[x][y-1]
웅덩이와 배열범위를 조심한다면 쉽게 해결할 수 있다.
배열 인덱스를 0부터 사용하지 않고, 1부터 사용하는 방식으로 설계하면 코드 구현이 쉬워진다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(m, n, puddles):
answer = 0
d = [[0 for _ in range(m+1)] for _ in range(n+1)]
for y, x in puddles:
d[x][y] = -1
d[0][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if d[i][j] == -1:
d[i][j] = 0
else:
d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000007
return d[n][m]