[python] 백준 1937 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

문제 해결

• 계속해서 그래프 안을 상하좌우 움직이고 갔단 곳은 안가므로(숫자가 증가 수열이므로) DFS 사용하는 것이 좋을 것이다.
• 그런데 그냥 쓰면 당연히 시간초과가 날 것이다. 이전에 방문해서 결과를 냈던 것은 저장을 하는 것이 필요하다.
• 그러기 위해서는 dp를 사용해서 이전에 (r,c) 좌표에서 DFS 시작했을 때 최댓값이 dp[r][c] 였다.라고 저장되어있으면 넘어간다.

 

CODE

import sys
sys.setrecursionlimit(100000)
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
move = [(-1,0), (0,1), (0,-1),(1,0)]
ans = 0
def dfs(r,c):
    if dp[r][c]: return dp[r][c]
    dp[r][c] = 1
    for next in move:
        new_r = r + next[0]
        new_c = c + next[1]
        if new_r<0 or new_r>=n or new_c<0 or new_c>=n: continue
        elif A[new_r][new_c] > A[r][c]:
            dp[r][c] = max(dp[r][c], dfs(new_r,new_c)+1)
    return dp[r][c]

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

print(ans)