욕심쟁이 판다 (백준 1937)

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

1937번: 욕심쟁이 판다

 

dp, dfs를 이용해서 그래프 탐색을 진행하는 재귀함수를 만들어서 풀었다. 

import sys 
input = sys.stdin.readline 
sys.setrecursionlimit(300000)
n=int(input())
arr= [list(map(int, input().split())) for _ in range(n)] 
dp = [[0]*(n) for _ in range(n)]
visited = [[0]*(n) for _ in range(n)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = 0 

def find(x,y): 
    if dp[x][y]!=0: return dp[x][y] 
    visited[x][y] = 1 
    for i in range(4):
        newx,newy=x+dx[i],y+dy[i] 
        if newx<0 or newy<0 or newx>=n or newy>=n : continue 
        elif visited[newx][newy]!=0 or arr[x][y]>=arr[newx][newy] : continue
        else:
            dp[x][y]= max(dp[x][y] ,find(newx,newy)+1 )
    visited[x][y] = 0
    return dp[x][y] 

for i in range(n):
    for j in range(n):
        ans =max(ans, find(i,j))
print(ans+1)