1937 욕심쟁이 판다 [Python]

문제대로 2차원 배열을 이용한 맵을 만든후 1,1 위치부터 판다가 살수 있는 최대일수를 구하는 방식으로 구현했다.

최대일수 구하는 방법은 dfs를 이용하였으며 재귀를 통해 방문될때마다 그 재귀를 호출한 스택에는 +1값을 주도록 하였다

최대일수가 메모되있으면 다른 행열을 찾아보는방식으로 시간을 절약하였다.

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


def dfs(y, x):
    cache[y][x] += 1
    for dy, dx in direct:
        cy = dy + y
        cx = dx + x
        if cy < 0 or cx < 0 or cy >= n or cx >= n:
            continue
        if matrix[y][x] < matrix[cy][cx]:
            if cache[cy][cx]:
                cache[y][x] = max(cache[y][x], cache[cy][cx] + 1)
            else:
                cache[y][x] = max(cache[y][x], dfs(cy, cx) + 1)
    return cache[y][x]


direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]

n = int(read())

matrix = []
for i in range(n):
    matrix.append(list(map(int, read().split())))
cache = [[0] * n for _ in range(n)]

k = 0
for i in range(n):
    for j in range(n):
        if cache[i][j] == 0:
            k = max(dfs(i, j), k)


print(k)