[Python] 백준 / gold / 1520 : 내리막길

문제 링크 : https://www.acmicpc.net/problem/1520

예전에 티스토리 블로그에 정리했던 DFS + DP 문제를 복습해봤다. https://heyksw.tistory.com/8

이 문제는 욕심쟁이 판다 https://velog.io/@heyksw/Python-백준-gold-1937-욕심쟁이-판다 문제랑 엄청 비슷하다. 판다 문제를 풀고 나서 이 문제를 복습해봐야겠다는 생각이 들어서 복습해봤는데, 역시 힘들었던 문제는 다시 풀어도 힘든거같다..

dp 문제를 풀 때는 dp[x][y] 의 의미가 뭔지 정확히하고 시작하는게 너무 중요하다. 특히 이 문제는 dp table 을 2가지 의미로 해석해서 2가지 풀이가 가능했다.

풀이방법 1

• dp[x][y] = (x, y) 에서 도착점까지 갈 수 있는 경로 수

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, sys.stdin.readline().split())
graph = []
dp = [[-1]*M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(N):
    graph.append(list(map(int ,sys.stdin.readline().split())))


# dp[x][y] = (x, y) 에서 도착점까지 갈 수 있는 경로 수
def dfs(x, y):
    # 도착점
    if x == N-1 and y == M-1:
        return 1
    # dp 값이 있는 경우
    if not dp[x][y] == -1:
        return dp[x][y]
    # dp 값이 없는 경우
    else:
        dp[x][y] = 0
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < N and 0 <= ny < M and graph[x][y] > graph[nx][ny]:
                dp[x][y] += dfs(nx, ny)
        return dp[x][y]


dfs(0, 0)
print(dp[0][0])

풀이방법 2

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, sys.stdin.readline().split())
graph = []
dp = [[-1]*M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(N):
    graph.append(list(map(int ,sys.stdin.readline().split())))


# dp[x][y] = (x, y)에서 시작점 까지 올라갈 수 있는 경로 수
def dfs(x, y):
    if x == 0 and y == 0:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < N and 0 <= ny < M and graph[x][y] < graph[nx][ny]:
                dp[x][y] += dfs(nx, ny)
        return dp[x][y]


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