백준 1937 - 욕심쟁이 판다 (Python)

https://acmicpc.net/problem/1937 

1937번: 욕심쟁이 판다

최댓값을 구하는 문제이니 어쨌거나 dp일 것이라 생각했다. dfs와 연관지어서 하기가 조금 헷갈렸다.
dfs를 할 때 특정 조건이면 return True(아니면 값)을 해서 하나의 경로를 찾는 것에 적응하자.

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

n=int(input())
graph=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(n)] for _ in range(n)]
answer=0

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

def dfs(cy,cx):
    if dp[cy][cx]:
        return dp[cy][cx]
    dp[cy][cx]=1
    for i in range(4):
        ny,nx=cy+dy[i],cx+dx[i]
        if 0 <= ny < n and 0 <= nx < n and graph[ny][nx] > graph[cy][cx]:
            dp[cy][cx]=max(dp[cy][cx],dfs(ny,nx)+1)
    return dp[cy][cx]

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