boj.kr/1937 욕심쟁이 판다 (gold3) 파이썬 풀이

1. dp 배열을 대나무숲 그래프의 크기만큼의 -1으로 초기화

2. dfs 함수를 다음과 같이 정의

2.1. y, x좌표를 인자로 받고 dp[y][x]값이 -1이면 0으로 갱신 후 아래를 수행

2.1.1. 상하좌우 좌표에 대해 유효한 좌표인지 검사하고 현재 좌표값보다 더 큰 값이면

dp[y][x]에서 dfs[ny][nx]값과 dp[y][x]값 중 더 큰값으로 갱신

2.2. dp[y][x]+1한 값을 반환

3. 대나무숲의 모든 좌표를 순회하면서 dfs(y, x)한 값의 최대값을 저장하고 출력

 

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

dy = (-1, 1, 0, 0)
dx = (0, 0, -1, 1)

import sys
sys.setrecursionlimit(10**9)

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

ans = -1e9
for y in range(N):
    for x in range(N):
        ans = max(ans, dfs(y, x))

print(ans)

 

체크배열을 사용하고 검사하는 대신, dp배열의 초기값을 -1으로 저장하고 dfs에서 가장 먼저 검사하도록 함으로서 이미 dp배열에 최대값을 저장한 좌표에 대해서는 다시 탐색하지 않도록 해야한다. 왜냐하면 이렇게 하지 않으면 시간초과가 발생하기 때문이다.