백준 / 욕심쟁이 판다 / 1937번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 욕심쟁이 판다 / 1937번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/1937

 

문제 설명

---

나의 풀이

import sys
sys.setrecursionlimit(10**6)  # 재귀함수 깊이 제한


move = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 상 하 좌 우


def dfs(y, x):
    # 이미 계산된 경우 반환
    if dp[y][x] != 0:
        return dp[y][x]
    
    best = 1  # 최소 자기 자신 1칸
    current = bamboo[y][x]

    for ny, nx in move:
        iy, ix = ny + y, nx + x
        if 0 <= iy < n and 0 <= ix < n and bamboo[iy][ix] > current:
            best = max(best, 1 + dfs(iy, ix))
    
    dp[y][x] = best
    return best


if __name__=="__main__":
    n = int(input())
    
    bamboo = [list(map(int, input().split())) for _ in range(n)]  # 대나무
    dp = [[0] * n for _ in range(n)]  # dp

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

    print(ans)

---

※ 알아야 할 것

1. 이미 계산된 지역은 다시 가지 않는다. 

2. 가지 않았다면 더 탐색하도록 한다.