[python] 백준 욕심쟁이 판다

 

 

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

1937번: 욕심쟁이 판다

 

알고리즘: dp + dfs

 

1. 판다는 대나무를 먹고 상,하,좌,우로 이동한다. 하지만 여기서 제약 조건이 붙은데, 반드시 대나무가 더 많은 곳으로 이동해야 한다는 것이다.

 

2. 해당 조건을 토대로 dp의 메모제이션 기법을 사용 할 수 있다. 이동한 장소를 기준으로 얼마나 생존할수 있는지를 계산해 각 생존일을 장소 마다 저장시키면 된다. 

 

3. for문을 돌며, 시작 장소를 정한다. 시작 장소 기준으로 가장 긴 생존시간을 계산하면 완료

 

특이사항

 

문제를 푸는데 끊임없이 런타임 에러 (RecursionError) 가 발생하였다. 이를 해결 하기 위해

 

1)  python의 재귀 제한 (recursionlimit)은 기본 설정이 1000으로 매우 제한적이다. 이를

sys.setrecursionlimit(10**6) 을 통해 수정하자.

 

2. 다음 장소로 이동을 체크하는 if문에서 and를 4번이나 설정 하였다. 이를 2번으로 줄여 주니 재귀 오류가 발생하지 않았다...

 

        if nx < n and nx > -1 and ny < n and ny > -1 and forest[nx][ny] > curCost:
            d[x][y] = max(dp(nx,ny) +1, d[x][y])

to

        if n >nx >=0 and n>ny>=0 and forest[nx][ny] > curCost:
            d[x][y] = max(dp(nx,ny) +1, d[x][y])

 

전체 코드

# https://www.acmicpc.net/problem/1937
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def dp(x, y):
    if d[x][y] > -1:
        return d[x][y]
    
    curCost = forest[x][y]    
    d[x][y] = 1
    for i in range(4):
        nx= x + dx[i]
        ny= y + dy[i]
        if n >nx >=0 and n>ny>=0 and forest[nx][ny] > curCost:
            d[x][y] = max(dp(nx,ny) +1, d[x][y]) 

    return d[x][y]

n = int(input())
d = [[-1]*n for _ in range(n)]
forest = [[] for _ in range(n)]

for i in range(n):
    forest[i] = list(map(int,input().split(" ")))
answer = 0 

for i in range(n):
    for j in range(n):
        answer = max(dp(i ,j), answer)

print(answer)