[DFS, DP] 백준 내리막길 1520번 with Python3 ★★

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

1520번: 내리막 길

문제

정답 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

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

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

m, n = map(int, input().split())
s = [list(map(int, input().split())) for i in range(m)]
dp = [[-1] * n for i in range(m)]

print(dfs(m - 1, n - 1))

출처:https://chldkato.tistory.com/114

https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-1520-%EB%82%B4%EB%A6%AC%EB%A7%89%EA%B8%B8-Python

해석

dfs에 dp또한 적용시켜 이미 지나온 길을 다시 반복하지 않게끔 되어있다. 

아직 이해는 못했다. 

 

 

 

내 풀이 -실패-

import sys
input = sys.stdin.readline

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def dfs(x, y):
    global count

    now = slide[x][y]
    visited[now] = 1

    if x == m-1 and y == n-1:
        count += 1
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (0 <= nx < m) and (0 <= ny < n):
            next = slide[nx][ny]
            if now > next and visited[next] == 0:
                visited[next] = 1
                dfs(nx, ny)
                visited[next] = 0


# 입력
m,  n = map(int, input().split())
# m 세로 / 행 | n 가로 / 열
slide = [list(map(int, input().split())) for _ in range(m)]
temp = slide[0][0] + 1
visited = [0] * temp
count = 0
dfs(0, 0)
print(count)

해설

문제 풀이를 위해서는 dfs 알고리즘을 사용해야한다고 보았는데, 시간초과가 떴다. 

이 시간초과 상황을 해결하기위해 추가적인 방법들을 고려해봤지만 마땅히 떠오르지 않았다.