백준 1937 욕심쟁이 판다

문제

코드

import sys
sys.setrecursionlimit(10**6)
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1]*n for _ in range(n)]
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def dfs(y, x):
    for dy, dx in d:
        newy = y+dy
        newx = x+dx

        if newy >= n or newy < 0 or newx >= n or newx < 0:
            continue

        if dp[newy][newx] != -1:
            if board[newy][newx] > board[y][x]:
                dp[y][x] = max(dp[newy][newx]+1, dp[y][x])
            continue

        if board[newy][newx] > board[y][x]:
            dp[y][x] = max(dp[y][x], dfs(newy, newx)+1)
        elif dp[y][x] == -1:
            dp[y][x] = 0

    return dp[y][x]


answer = 0
for i in range(n):
    for j in range(n):
        dfs(i, j)
for i in range(n):
    for j in range(n):
        answer = max(dp[i][j], answer)
print(answer+1)

풀이

dp로 풀이 했습니다

2중 for문으로 모든 값들을 순회돌면서 dfs를 통해 dp값을 채워줬는데 이때 한 번 방문한 곳들에서 가장 멀리 갈 수 있는 값들을 dp에 저장해두면 재방문을 할 필요가 없어집니다

예제 입력이 들어온 경우

이런식으로 dp 배열이 채워집니다 각각의 값들은 현재 자리에서 가장 깊게 들어갈 수 있는 길이를 의미 합니다

파이썬으로 풀이하니까 재귀 호출 깊이에 제한이 걸려서 아래 코드를 추가해줬습니다

import sys
sys.setrecursionlimit(10**6)