공부/알고리즘 문제
[백준] BOJ 1937번 욕심쟁이 판다
_eun
2020. 12. 11. 21:54
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서
www.acmicpc.net
from sys import setrecursionlimit
setrecursionlimit(10**9)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
dp = [[0]*501 for _ in range(501)]
N = int(input())
bamboo = []
result = 0
def dfs(i, j):
if dp[i][j]: return dp[i][j]
dp[i][j] = 1
for k in range(4):
if i+dx[k] == -1 or i+dx[k] == N or j+dy[k] == -1 or j+dy[k] == N:
continue
if bamboo[i][j] < bamboo[i+dx[k]][j+dy[k]]:
dp[i][j] = max(dp[i][j], dfs(i+dx[k], j+dy[k])+1)
return dp[i][j]
bamboo = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
for j in range(N):
result = max(result, dfs(i, j))
print(result)
728x90