백준 1520 내리막 길 python

어려운 DP.. 꾸준히 연습해보고 있지만 빠른 시간안에 생각해 내고 풀이하는게 아직은 어렵다

📜 문제 바로 가기 : 내리막 길

제출코드

파이썬

import sys
sys.stdin = open('ee.txt', 'r')
input = sys.stdin.readline

sys.setrecursionlimit(5000)

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [[-1] * M for _ in range(N)]
visit[0][0] = 1

def isRange(i, j):
    if 0 <= i < N and 0 <= j < M:
        return True
    return False

delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def DP(i, j):

    roads = 0
    for di, dj in delta:
        pi, pj = i - di, j - dj
        if isRange(pi, pj) and arr[i][j] < arr[pi][pj]:
            if visit[pi][pj] == -1:
                roads += DP(pi, pj)
            else:
                roads += visit[pi][pj]

    visit[i][j] = roads
    
    return roads    

print(DP(N-1, M-1))

---

접근방법

우선 기본적인 방법은 DP접근은 아래와 같다.

i, j에 올 수 있는 경우의 수는
(i-1, j), (i+1, j), (i, j-1), (i, j+1) 상하좌우 4방향까지 올 수 있는 경우의 수를 모두 더한 것과 같다.

내리막 길로만 이동이 가능함으로 무한 루프에 빠지는 경우는 없을 것이다.

첫번째 생각 : BFS + DP(DFS)

(i, j) 에 도착하는 경우의 수를 구할 때 (i-1, j)에서 가는 값을 구할 때
그 값 = (i-1, j)까지의 경우의 수 x (i-1, j)에서 (i, j) 로 가는 경우의 수

이렇게 생각한 이유는 (i-1, j) 에서 (i, j) 가는 경로가 직진외에도 우회해서 가는 경우가 있으므로 BFS를 이용해 찾아줘야 된다고 생각했다.

결론으로 이 방법은 잘못된 방법이었는데 우회를 한다고 해도 결국엔 4방향 중 한곳으로 들어올 것이고 이는 4방향을 다 계산하기 때문에 중복이 생겨 가지수가 정답보다 커지게 된다.

두번째 생각 : BFS 없이 DP(DFS)

BFS 방식이 잘 못된다는 것을 알고 이를 지웠다.
이제 단순히 (i-1, j), (i+1, j), (i, j-1), (i, j+1) 의 값을 더하는 것으로 (i, j) 값을 구한다.

이 방법은 작은 케이스에서는 정답을 낼 수 있었지만 이미 계산했던 값도 다시 계산하기 위해 재귀를 수행했기 때문에 큰 케이스에서는 시간초과가 나왔다.

세번째 생각 : + 방문값

시간초과를 해결하고자 방문 배열을 만들어줬다. visit 배열을 만들어 초기값을 -1 로 설정해 주고 계산이 끝나면 값을 기록한다.

이를 이용해 visit[i][j] 값이 -1 이 아니라면 이미 계산된 값이 있으므로 재귀를 타지 않고 방문값을 이용한다.

이 방법으로 문제를 해결할 수 있었다!