이전에 BFS를 이용하여 풀었는데, 코드가 너무 지저분해서 DFS와 DP로 해결한 문제.
1. 요약
집에서 출발하여 학교로 갈 때, 웅덩이들을 피하면서 최단 경로로 가야한다. 여기서 우리가 구해야 하는 답은 최단 경로의 수이다.
2. 아이디어
- 문제에서 좌표는 (x, y)로 표현한다.
- 집은 (1, 1)에 있고 학교는 (m, n)에 있고, 오직
→,↓방향으로만 이동한다.- 위의 사실로부터, 특정 지점을 경유하여, 학교로 갈 때, 집에서 특정 지점까지의 거리는 항상 최단거리이다. 따라서, 특정 지점(x, y)을 경유하여 학교로 가는 경로의 수를 메모이제이션한다.
- 학교에 도착하면 하나의 경우가 만들어지므로, 1을 반환한다. 이후 반환된 1을, 특정 지점(x, y)을 경유하여 학교로 가는 경로의 수에 더한다.
3. 코드
d = [[1,0], [0,1]]
dp = []
r, c = 0, 0
_puddles = []
def isin(y,x):
global r, c
if -1<y<r:
if -1<x<c: return True
return False
def dfs(y, x):
if [y, x] == [r-1, c-1]: return 1
if dp[y][x] != 0: return dp[y][x]
for i in range(2):
ny = y + d[i][0]
nx = x + d[i][1]
if isin(ny, nx):
if [nx+1, ny+1] in _puddles: continue
dp[y][x] += dfs(ny, nx)
return dp[y][x]
def solution(m, n, puddles):
global dp, r, c, _puddles
r, c = n, m
_puddles = puddles
dp = [[0 for _ in range(m)] for _ in range(n)]
answer = dfs(0,0)
return answer % 1000000007