[백준] 1520번 내리막 길

사용 언어 - Python3

문제 -  1520번 내리막 길

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

1520번: 내리막 길

 

 

정답

2차원 그래프의 DP

# 모든 점을 방문
# 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다
# 재귀로 구현한 뒤 DP로 바꾼다.

 

현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex

ey = y + dy, ex = x + ex

 

조건1) ex,ey가 m*n 그래프 안에 있어야함

조건2) 이동하는 곳의 값이 더 작아야함 graph[y][x] > graph[ey][ex]

조건3) 0,0에서 시작

조건4) dp = n*n의 -1 행렬 // dp가 -1이 아니면, 다시 구할 필요 없어야 함

 

 

route = 0

=> 조건 만족시

route += recur(ey,ex) 

한번 이동시 +1

끝까지 이동했다면, (m-1,n-1)에 도착했다면, return 1

(3번 이동시, route  = +1+1+1+1 = 4)

 

dy[y][x] = route 경로의 개수 dp에 저장

return dp[y][x]

def recur(y,x):
    if y == m-1 and x == n-1:
        return 1
    
    if dp[y][x] != -1:
        return dp[y][x]
    
    route = 0
    for dy, dx in [[0,1],[0,-1],[1,0],[-1,0]]:
        ey = y + dy
        ex = x + dx
        if 0 <= ey < m and 0 <= ex < n:
            if graph[y][x] > graph[ey][ex]: # 작은값으로 이동
                route += recur(ey,ex)
    dp[y][x] = route
    
    return dp[y][x]

m, n = map(int,input().split()) # 세로 m 가로 n
graph = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1 for _ in range(n)] for _ in range(m)]

answer = recur(0,0) # 0,0 에서 시작
print(answer)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1520_%EB%82%B4%EB%A6%AC%EB%A7%89%EA%B8%B8.py

 

 

• 19947번 욕심쟁이 판다 문제랑 매우 유사!

https://rladuddms.tistory.com/434

[백준] 19947번 욕심쟁이 판다