백준 1520번: 내리막 길 (Python)

접근

DFS와 DP를 동시에 이용하면 쉽게 풀 수 있는 문제였다.

visited라고 이름붙인 함수를 -1로 초기화하고, 이동 시 0으로 다시 설정해준다.

1. 과정을 진행하면서 visited에 저장된 값이 0이면 목적지에 도달하지 못하므로 0을 return 해준다.
2. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다.
3. -1 이면 방문하지 않은 경로이므로 dfs 수행

코드

import sys

sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
height = []
for _ in range(n):
    height.append(list(map(int, sys.stdin.readline().split())))
visited = [[-1 for _ in range(m)] for __ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def route(x, y):
    if x == n - 1 and y == m - 1:
        return 1
    if visited[x][y] != -1:
        return visited[x][y]
    visited[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if height[nx][ny] < height[x][y]:
                visited[x][y] += route(nx, ny)
    return visited[x][y]


print(route(0, 0))

더 생각해 볼 것?

dfs를 이용해야 한다고 어렴풋 생각하고도 dp만 이용해서 풀려다가 풀지 못하고 dfs를 이용하여 풀었다. 문제를 보고 어떤 알고리즘을 써야한다고 갇히지 말고 유연하게 생각해보아야 겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!