[백준] 1937번 욕심쟁이 판다 ★★★

💡문제접근

• 처음엔 이 문제에서 왜 깊이 우선 탐색이 사용되는지 몰라서 단순 방향 배열을 이용한 dp문제로 생각해서 코드를 짰는데 바로 WA를 받았다. dp로 접근을 하게 되면 특정 시작점에서부터 탐색을 시작하면서 dp 테이블의 값이 갱신이 되는데 다른 시작점에서 새롭게 탐색을 진행하게 된다면 이미 갱신된 dp 테이블로 인해서 결과값이 올바르게 나올 수 없기 때문에 DFS + dp로 접근을 해야한다.
• 좌표 개념에서의 완전 탐색 문제라고 바로 BFS로 문제를 푸는 행동은 자제해야 할 것 같다.

💡코드(메모리 : 51460KB, 시간 : 1124ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def DFS(y, x):
    if dp[y][x] != -1:
        return dp[y][x]
    dp[y][x] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        else:
        	# 이동한 지점이 대나무 양이 그 전 지점의 대나무 양보다 많아야 이동 가능
            if forest[y][x] < forest[ny][nx]:
                dp[y][x] = max(dp[y][x], DFS(ny, nx) + 1)
    return dp[y][x]

n = int(input())
forest = []
for _ in range(n):
    forest.append(list(map(int, input().strip().split())))

dp = [[-1] * n for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
Max = 0
for i in range(n):
    for j in range(n):
        Max = max(Max, DFS(i, j))
print(Max)

💡소요시간 : 56m