[알고리즘/DP] 1520번 : 내리막 길 - python

링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

---

• 문제
• 소요시간: 30분(참고)

---

• 설계하기(접근방법) 

1. 입력받기

행렬을 일력받는다

 

2. 구현하기

이 문제는 dfs와 dp를 섞은 문제이다

 

행렬이 커져서 dfs를 전부 탐색하게 된다면

시간초과가 날 것이다

 

그래서 시간 초과를 줄이기 위해서는

이미 갔던 길에 대해서 메모이제이션을 할 필요가 있다

 

또 다른 dfs를 할 때 이미 탐색이 전부 완료된 갔던 길을 만났고

그 길에 대해서 다시 탐색할 필요가 없다

 

그냥 경우의 수를 더해주면 된다.

 

즉 갈림길 마다 dfs를 탐색하고

 

그 갈림길이 끝나면 갈림길에 대해서 탐색했던 모든 경우의 수를

더해 갈림길에 append하면 된다

 

3. 출력하기

0,0 에서 탐색을 마친 dfs 값을 출력한다

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline
sys.setrecursionlimit = (10 ** 8)

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x,y):
    # 끝에 도달하면 경우의 수 1을 리턴
    if x == m - 1 and y == n - 1:
        return 1
    
    # 방문한적이 있으면 그 경우의 수 리턴
    if dp[x][y] != -1:                       
        return dp[x][y]

    ways = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < m and 0 <= ny < n:
            if graph[x][y] > graph[nx][ny]:
                ways += dfs(nx,ny)
        
    dp[x][y] = ways
    return ways
                

## 

## 가로 세로
m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1 for _ in range(n)] for _ in range(m)]
print(dfs(0,0))

---

• 얻어갈 부분

1. dfs와 dp를 결합한 문제였다. 로직은 생각했지만 구현을 어떻게 할지 몰라 블로그를 참고했다