[백준알고리즘] 1937번: 욕심쟁이 판다 -Python

[백준알고리즘] 1937번: 욕심쟁이 판다 -Python

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

1937번: 욕심쟁이 판다

재귀를 사용한 동적 계획법으로 문제를 풀었다.

 

시작점이 주어지지 않았기 때문에 각각의 지점이 시작점일 때 가장 오래 생존할 수 있는 일수를 구해야 한다.

 

리스트 visited에서는 각 지점을 방문했을 때를 포함해 앞으로 며칠을 더 살 수 있는지를 저장해놓는다. 이후 경로는 생각하지 않아도 최대 일수만 유지하고 있으면 된다.

from sys import setrecursionlimit
setrecursionlimit(10**9)

def dfs(i, j):
    if visited[i][j] < 0:
        visited[i][j] = 0
        for d in range(4):
            x, y = i+dx[d], j+dy[d]
            if 0<=x<n and 0<=y<n and forest[i][j] < forest[x][y]:
                visited[i][j] = max(visited[i][j], dfs(x, y))
        visited[i][j] += 1
    return visited[i][j]

n = int(input())
forest = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * n for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, dfs(i, j))
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다