[백준 - Python] 1937 - 욕심쟁이 판다

0.  문제 링크

 

 

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

1937번: 욕심쟁이 판다

---

1.  풀이 방법

 

 

이 문제는 DFS + DP이다.

안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다.

 

https://minny27.tistory.com/42

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

 

결론적으로 이 분의 블로그를 참고했다.

내가 설명하는 것보다 이 분의 블로그가 더 자세히 설명할 것이다.

이런 류의 문제를 보다보면, 점점 사고가 확장되는 것 같아서 좋다.

---

2.  코드

 

 

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


def dfs(y, x):
    if dp[y][x]:
        return dp[y][x]
    else:
        dp[y][x] = 1
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < n:
                if maps[ny][nx] > maps[y][x]:
                    dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1)
        return dp[y][x]


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

    dir = [[-1, 0],[1, 0],[0, -1],[0, 1]]

    ans = 0
    for i in range(n):
        for j in range(n):
            if not dp[i][j]:
                ans = max(ans, dfs(i, j))
    
    print(ans)

---

3.  마무리