1937번 욕심쟁이 판다

문제

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

접근 방식

DP를 활용한 DFS 방식으로 풀 수 있다.

처음에 완전탐색, 순수 DFS로 접근한다고 간주하면, 최악의 경우 500 * 500번 탐색을 수행하므로 아마 시간초과 걸릴 것이다. 여기서 한번이라도 탐색한 칸은 최대 몇칸까지 갈 수 있는지를 캐싱해두면 시간이 단축될 것이다.

그러면 DP 문제 영역은 해당 칸에서 최대 몇 칸을 갈 수 있냐가 될 것이고, 이에 따라 DFS 함수 알고리즘을 짤 수 있다.

dfs(i, j) -> 최대로 움직일 수 있는 칸 수 연산

- 한번이라도 방문한 적이 있다면 바로 dp값 반환
- 없다면 해당 칸에 대해 dfs 탐색 수행해서 최대한 많은 칸을 간다:
  dp[i][j] = max(dfs(i+di, j+dj), dp[i][j])
  

코드

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline


def dfs(cx, cy):
    if dp[cx][cy] == 0:
        dp[cx][cy] = 1

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if 0 <= cx + dx < n and 0 <= cy + dy < n and MAP[cx + dx][cy + dy] > MAP[cx][cy]:
                dp[cx][cy] = max(dfs(cx + dx, cy + dy), dp[cx][cy])

    return dp[cx][cy] + 1


n = int(input())
MAP = [list(map(int, input().split())) for _ in range(n)]

res = 0
dp = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        res = max(res, dfs(i, j) - 1)

print(res)