[python] 백준 - 1520 (내리막 길)
골드3 문제이며, 제한 시간은 2초이다.
문제
해결 과정
DFS문제임은 바로 보였다. 처음에 생각한 해결 과정은 DFS를 돌려서 n - 1, m - 1까지 도착한 경우가 몇 개인지 세는 방식을 생각하였다. 하지만 이 방식은 답은 구해지지만 시간 복잡도가 커질 수 있다. 따라서 메모이제이션 기법을 활용해서 각 지점마다 경로의 수가 몇 개인지 저장해놓고, 그 지점에 도착하면 기록해둔 경로의 개수를 더해주는 방식으로 해결했다.
풀이
def dfs(x, y):
if x == n - 1 and y == m - 1:
return 1
if dp[x][y] != -1:
return dp[x][y]
dp[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] < graph[x][y]:
dp[x][y] += dfs(nx, ny)
return dp[x][y]
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dp = [[-1 for _ in range(m)] for _ in range(n)]
answer = dfs(0, 0)
print(answer)DFS 구현은 그리 어렵지 않았지만, 메모이제이션을 사용해서 시간 복잡도를 줄인다는 생각을 못했었다. DP에 대한 연습이 더 필요하다!
댓글
0아직 댓글이 없습니다.