[백준 1937 욕심쟁이 판다 문제] PYTHON

 

이 문제는 출발점이 정해져있지 않기때문에 시간 복잡도에 더 유의해야한다.

또한, 방문했던 노드에서 가질 수 있는 최댓값(이동거리)은 동일하기 때문에

이를 저장하여 사용하도록 한다. (DP+DFS)

 

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10**9)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
input = stdin.readline
answer = 0


def DFS(i, j):
    if visit[i][j] < 0:
        visit[i][j] = 0
        for k in range(4):
            xindex = i+dx[k]
            yindex = j+dy[k]
            if 0 <= xindex < N and 0 <= yindex < N and Pgraph[i][j] < Pgraph[xindex][yindex]:
                visit[i][j] = max(visit[i][j], DFS(xindex, yindex))
        visit[i][j] += 1
    return visit[i][j]


N = int(input())
Pgraph = []
visit = [[-1] * N for i in range(N)]

for _ in range(N):
    Pgraph.append(list(map(int, input().split())))

for i in range(N):
    for j in range(N):
        answer = max(DFS(i, j), answer)

print(answer)