[백준 1937] 욕심쟁이 판다(Python)

BFS/DFS로 풀다가 시간초과나서 해설을 본 문제.

1. 요약

판다는 현재 위치에서 상,하,좌,우로 1칸 이동 할 수 있는 능력이 있고, 이동 할 때 1일이 걸린다. 하지만 판다가 실제로 움직일 때는 판다의 현재 위치보다, 다음 위치의 대나무 수가 많을 때이다. 대나무를 먹지 않으면, 판다는 죽는다. 판다의 현재 위치를 우리가 정할 수 있을 때, 판다가 가장 오래 살 수 있는 일 수를 구해야한다.

2. 아이디어

판다가 오래 사는 일수 == 판다가 가장 많이 이동한 횟수(최장 경로) + 1

메모이제이션 없이 BFS/DFS로 구현하게 되면, 최장 경로를 구하는 과정에서, 이미 방문한 곳을 재방문하여, 연산을 다시하게되는 경우가 발생한다. 이후, 이미 방문한 곳에 대해, 큐에 다시 삽입되거나, 재귀함수가 다시 호출된다. 이는 시간초과를 유발한다. 따라서 다이나믹 프로그래밍으로 해결해야한다.

현재 위치가 arr[i][j]로 주어졌을 때, arr[i][j]를 시작점으로 하여, 움직일 수 있는 최장경로를 기록한다.(메모이제이션)

자세한 내용은 https://yabmoons.tistory.com/154를 참조하면 된다.

3. 코드

import sys
from collections import deque

sys.setrecursionlimit(40000)
n = int(sys.stdin.readline().rstrip())
arr = []
dp = [[-1 for _ in range(n)] for _ in range(n)]
d = [[1,0], [-1,0], [0,1], [0,-1]]
answer = 0

for i in range(n):
    x = list(map(int, sys.stdin.readline().rstrip().split()))
    arr.append(x)

def isin(y,x):
    if -1<y<n:
        if -1<x<n: return True
    return False

def dfs(y, x):
    global dp, answer
    
    if dp[y][x] != -1: return dp[y][x]

    tmp = 0
    dp[y][x] = 1

    for i in range(4):
        ny = y + d[i][0]
        nx = x + d[i][1]

        if isin(ny, nx):
            if arr[ny][nx] > arr[y][x]:
                tmp = max(tmp, dfs(ny, nx))
        
    dp[y][x] += tmp
    
    if answer < dp[y][x]: answer = dp[y][x]

    return dp[y][x]


for i in range(n):
    for j in range(n):
        dfs(i, j)

print(answer)