[백준 / Python] 욕심쟁이 판다_1937

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

 

 

정답 코드

n = int(input())
data = []
dp = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    data.append(list(map(int, input().split())))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]


def dfs(x, y):
    if dp[x][y]:
        return dp[x][y]

    dp[x][y] = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and data[nx][ny] > data[x][y]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)
    return dp[x][y]


result = 0
for i in range(n):
    for j in range(n):
        result = max(result, dfs(i, j))
print(result)

 

dfs로 dp가 값이 있다면, 이미 해당 지점에서 가장 멀리 갈 수 있는 길이를 구했다고 판단하고

dp[x][y]를 반환한다.

만약에 해당 지점에서의 최장거리를 구하지 않았다면, dp[x[[y]를 1로 초기화 한 다음에, 

dfs를 재귀호출하여 1씩 값을 더해주며 최장거리를 구해준다.