[백준] 1937번 욕심쟁이 판다 - 파이썬/DFS

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

1차 풀이

import sys
sys.setrecursionlimit(10**6)


N = int(input())

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

def dfs(a,b,visited,graph,cnt,ans_list):

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    arround_check = True # True면 주변에 넘어갈 곳이 없음

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0<=nx<N and 0<=ny<N:
            if graph[nx][ny] > graph[a][b]:
                arround_check = False

    if arround_check:
        ans_list.append(cnt)
        return


    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]


        if 0<=nx<N and 0<=ny<N:
            if not visited[nx][ny] and (graph[nx][ny] > graph[a][b]):
                visited[nx][ny]=True
                dfs(nx,ny,visited,graph,cnt+1,ans_list)
                visited[nx][ny]=False

for i in range(N):
    for j in range(N):
        visited = [[False for _ in range(N)] for _ in range(N)]
        ans_list = []
        dfs(i,j,visited,graph,1,ans_list)
        DP[i][j] = max(ans_list)


print(DP)

시간초과가 발생했다.

DP를 적용시키지 못했다.

2차 풀이

import sys
sys.setrecursionlimit(10**6)


N = int(input())

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

def dfs(a,b):

    if DP[a][b]:
        return DP[a][b]

    DP[a][b]=1

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0<=nx<N and 0<=ny<N:
            if graph[nx][ny] > graph[a][b]:
                DP[a][b] = max(DP[a][b],dfs(nx,ny) + 1)

    return DP[a][b]


for i in range(N):
    for j in range(N):
        answer = max(answer,dfs(i,j))


print(answer)

DP로 DFS의 반복을 줄이는 것이 핵심이다.