m | n | puddles | return |
---|---|---|---|
4 | 3 | [[2, 2]] | 4 |
최단경로의 개수이므로 dp를 이용하여 푼다.
행, 열 좌표가 반대. 0행n열일 때 웅덩이가 있으면 그 이후는 모두 갈 수 없는 길.
n행0열일때에도 마찬가지
def solution(m, n, puddles):
maps = [[1]*m for _ in range(n)]
for y, x in puddles:
x -= 1
y -= 1
maps[x][y] = 0
if x == 0:
for i in range(y, m):
maps[0][i] = 0
if y == 0:
for i in range(x, n):
maps[i][0] = 0
for i in range(1, n):
for j in range(1, m):
if maps[i][j] != 0:
maps[i][j] = maps[i-1][j]+maps[i][j-1]
return maps[-1][-1]%1000000007
def solution(m, n, puddles):
maps = [[0] * (m+1) for _ in range(n+1)]
maps[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
continue
if [j, i] in puddles:
maps[i][j] = 0
else:
maps[i][j] = maps[i-1][j] + maps[i][j-1]
return maps[-1][-1] % 1000000007