백준(1520) - 내리막길 Python

백준(1520) - 내리막길

문제풀이: DP, DFS, 파이썬

시작점부터 끝점까지 도착가능한 모든 경우의 수를 찾는 문제이다.

단순히 BFS나 DFS를 사용하게되면 이동했던 경로를 중복 검색하게되어 시간초과 오류가 발생하므로

한번 탐색한 경로는 더 이상 탐색하지 않도록 해야 한다.

문제예시로 동작 원리를 그려서 설명하면 아래와 같다.

1. 초기 DP 테이블

   

2. 첫번째 방법순회후 DP 테이블

1. 두 번째 방법순회후 DP 테이블

1. 세번째 방법순회후 DP 테이블

from collections import deque
import sys
input = sys.stdin.readline

# 이동방향 설정
mx = [0, 0, 1, -1]
my = [1, -1, 0, 0]

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

def dfs(x, y):
    # 도달가능하면 1을 리턴
    if x == (n-1) and y == (m-1):
        return 1
    # 방문하지 않았던 곳이라면 0으로 초기화
    if dp[x][y] == -1:
        dp[x][y] = 0

        now = arr[x][y]
        # 4가지 방향 조회
        for i in range(4):
            dx = x + mx[i]
            dy = y + my[i]
            if 0 <= dx < n and 0 <= dy < m:
                if now > arr[dx][dy]:
                    dp[x][y] += dfs(dx, dy)
    return dp[x][y]

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

print(dfs(0, 0))
print(dp)