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

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

1937번: 욕심쟁이 판다

---

💡문제이해 : 욕심쟁이 판다는 상,하,좌,우로 이동할 수 있는데 단 머물러 있던 자리보다 대나무가 많아야 한다. 

즉, 더 큰 수로만 이동할 수 있다. 최대한 많은 칸을 이동할 때 칸의 수를 구해라. 

 

🤔 만일 2에서 이동한다고 하면 2→ 5 →11 →15  , 2→ 15,  2→ 13,  2→ 16으로 이동 가능 

 

---

1. 대나무 숲 정보 입력받아오기 

n = int(input())
arr = [list(map(int,input())) for _ in range(n)]

 

2. 재귀함수로 갈 수 있는 경우의 수 구하기 

• 아무것도 방문하지 않았을 때 point = 0으로 설정 
• 상,하,좌,우 4가지 방향으로 탐색 
• 만일 이동하고자 하는 좌표가 그래프 안에 있고, 더 크다면 방문하여 point 업데이트 

def recur(y,x) :
	
    point = 0
    
    # 4가지 방향으로 탐색 
    for dy,dx in [[-1,0],[1,0],[0,1],[0,-1]] :
    	ey,ex = y+dy , x+dx
        #이동하는 좌표가 그래프 안에 있고
        if 0<= ey < n and 0<= ex < n : 
        	#해당 좌표보다 큰 곳으로 이동
            if arr[y][x] < arr[ey][ex] :
            	#너가 이동하여 한번이라도 방문했다면 point update 
            	point = max(point,recur(ey,ex) + 1))	
	
    return point

 

3. 모든 좌표에서 탐색 (좌표와 경우의 수 출력) 

for y in range(n) :
	for x in range(n) :
    	answer = recur(y,x)
        print(y,x,answer)

⇒ 실행결과 

(0,0) 좌표에서 갈 수 있는 최대 이동 횟수 : 0

(0,1) 좌표에서 갈 수 있는 최대 이동 횟수 : 2

(0,3) 좌표에서 갈 수 있는 최대 이동 횟수 : 1 

 

                               ⁝

 

 

 

 

 

 

4. DP로 변경

def recur(y,x) :

    if dp[y][x] != 0 :
    	dp[y][x]
    
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]] : 
        ey,ex = y+dy , x+dx 

        if 0 <= ey < n and 0 <= ex < n :
            if graph[y][x] < graph[ey][ex] :    
                dp[y][x] = max(dp[y][x] , recur(ey,ex) +1)
     
     return dp[y][x]
 
n =int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for i in range(n) for _ in range(n)] 


for y in range(n) : 
    for x in range(n) :
        recur(y,x)
        
        
print(dp)

#최대 칸의 개수 출력 
print(max(map(max,dp)) + 1 )

#실행결과 4 

 

---

위와 같이 풀었을 때 시간초과가 나버렸다.. 🤔