Baekjoon 1520. 내리막 길 / Python

1520. 내리막 길

난이도 : 골드 3
소요 시간 : 20분
날짜 : 2025.01.09
언어 : 파이썬
알고리즘 유형 : dp, bfs

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 높이가 담겨있는 그래프가 주어진다.
2. 내리막길로만 이동해서 1,1부터 m,n까지 이동하는 경우의 수를 구하기

2. 해결 방식

1. dp[i][j] : i,j에서의 이동가능한 경우의 수
2. 거꾸로 탐색하여 dp값을 채운다.
3. 재귀함수 : sol(x,y)
   • x,y : 현재 위치
   • x,y가 -1이 아니면 방문한 경우이므로, 종료
   • dp의 값을 0으로 초기화 시킨 후, 다음 방문 가능지역의 dp값을 더해준다.
   • 결과적으로 재귀함수의 특성때문에, 끝점부터 세는 구현방식이 된다.

3. 정답 코드

import sys;input=sys.stdin.readline
sys.setrecursionlimit(100000)

m, n = map(int, input().split())
heights = [list(map(int, input().split())) for _ in range(m)]

dp = [[-1] * n for _ in range(m)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def sol(x=0, y=0):
    if (x, y) == (m - 1, n - 1):return 1
    if dp[x][y] != -1:return dp[x][y]
    dp[x][y] = 0
    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if nx in range(m) and ny in range(n):
            if heights[nx][ny] < heights[x][y]:
                dp[x][y] += sol(nx, ny)

    return dp[x][y]

print(sol())