[BOJ] 1520번 내리막 길 / 사용언어 : 파이썬(python)

※ 문제링크  

1520번: 내리막 길

해당문제는 DFS와 DP를 활용해서 해결할 수 있는 문제로, 단순히 답만 출력하는 것은 DFS 또는 BFS코드만으로도 가능하나, 문제에서 요구하는 시간 및 메모리 조건을 충족시키기 위해서는 DP까지 활용하여 해결해야하는 문제였다. 주의해야할 점은 DP를 통해 방문한 경로들에 대해 따로 탐색을 하지 않게 조건을 작성할때 DP의 초기값을 0이 아닌 다른 값으로 주어야 한다는 것인데, 0으로 초기값을 주게되면 그 경로를 방문했으나 그 값이 0으로 저장될 수도 있기 때문에 중복탐색이 적용될 수도 있기 때문이다. 해당 부분만 주의해서 코드를 작성하면 통과가 가능하며, 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 2차원 배열로 그래프를 구현하고, 그래프의 크기만큼 DP를 만들어준다.

2. 상하좌우를 탐색하면서 경우의수를 확인할 DFS함수를 작성하고, 함수를 실행시켜준다.

3. 탐색종료 후 최종적인 값을 출력한다.(시간 및 메모리 단축을 위해 sys를 사용하였습니다.)

 

# DP의 개념과 DFS 혼합
def dfs(x, y):
    if x == M-1 and y == N-1:
        return 1
    
    if dp[y][x] != -1:
        return dp[y][x]
    
    value = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N and field[y][x] > field[ny][nx]:
            value += dfs(nx, ny)

    dp[y][x] = value
    return dp[y][x]
import sys
sys.setrecursionlimit(1500)
# input = sys.stdin.readline
N, M = map(int, input().split()) # N: 가로의 크기, M: 세로의 크기 
field = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dp = [[-1 for _ in range(M)] for _ in range(N)]
print(dfs(0,0))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.