[코딩테스트][백준] 🔥 백준 1520번 "내리막길" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 10분

import sys
sys.setrecursionlimit(10**5)

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

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

dp=[[-1]*m for _ in range(n)]

def dfs(x,y):
    if (x,y)==(n-1,m-1):
        return 1
    if dp[x][y]!=-1:
        return dp[x][y]
    dp[x][y]=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if board[nx][ny]>=board[x][y]:
            continue
        dp[x][y]+=dfs(nx,ny)
    return dp[x][y]

print(dfs(0,0))

내리막길의 수 세기: DFS와 DP 활용하기! ⛰️📉

내리막길의 수를 세는 문제이다. 기본적인 2차원 배열에서 DFS를 통해 경로를 찾고 그 경로를 찾는 범위가 커서 그 범위를 DP로 줄이는 문제이다. 이 때 내리막길인지 아닌지만 탐색할 때 유의하며 n-1,m-1에 도착하면 탐색을 return 1을 하여 경로의 방법을 누적하는 식을 사용하면 된다.

이렇게 Python으로 백준의 "내리막길" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊