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

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

1937번: 욕심쟁이 판다

 

1️⃣ 먹은 대나무 수보다 많은 쪽으로만 이동하는 판다

2️⃣ 완탐으로 풀었다가 시간 초과

3️⃣ DFS + DP로 해결

 

import sys
sys.setrecursionlimit(100000)

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
count = [[0]*n for _ in range(n)]
Max = 0

def DFS(y, x):
    if count[y][x]: # 들린 적 있으면
        return count[y][x] # 본인 리턴

    count[y][x] = 1 # 초기값 넣어주기

    for i, j in dir:
        dy, dx = y+i, x+j
        if 0 <= dy < n and 0 <= dx < n:
            if board[dy][dx] > board[y][x]: # 대나무가 더 많이 있는 곳으로만 이동
                count[y][x] = max(count[y][x], DFS(dy, dx)+1)

    return count[y][x] # 상하좌우 중 먹을 수 있는 대나무가 없으면 본인 리턴

for y in range(n):
    for x in range(n):
        if count[y][x] == 0:
            Max = max(Max, DFS(y, x))

print(Max)

 

🐢 범위가 너무 커서 (대나무의 양이 1000000보다 작거나 같다) RecursionError를 피할 수 없었다ㅠㅠ

🐢 구글의 도움을 받은 결과 sys.setrecursionlimit(100000)로 파이썬의 재귀 깊이 제한을 수정해주었다.

🐢 파이썬은 최대 재귀 깊이가 1000으로 얕은 편이라, 코테에서 재귀 쓸 경우에는 저 코드를 써놓아야 하는 모양이다. 또 하나 배웠다...✏️