[BOJ-1937] 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

---

[코드 - Python3]

 

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

#상하좌우
dy=(-1,1,0,0)
dx=(0,0,-1,1)

def maxAge(y,x):
    global n, MAP, dp
    #현위치에 대한 최대수명이 0이 아니라면
    if dp[y][x]!=0:
        return dp[y][x]

    #현위치에 대한 최대수명이 0이다.
    dp[y][x]=1 #판다가 살 수 있는 수명은 최소 1일이다.
    for i in range(4):
        nexty=y+dy[i]
        nextx=x+dx[i]
        if (nexty>=0 and nexty<n) and (nextx>=0 and nextx<n):
            #다음위치의 대나무수가 현위치보다 더 많다면
            if MAP[nexty][nextx]>MAP[y][x]:
                #현위치의 최대수명= 현위치최대수명, 다음위치 최대수명+1 중 큰값
                dp[y][x]=max(dp[y][x], maxAge(nexty, nextx)+1)
    return dp[y][x]
                
if __name__=='__main__':
    n=int(input())
    #n*n 맵 입력
    MAP=[ [*map(int, input().strip().split())] for _ in range(n)]

    dp=[ [0]*n for _ in range(n)]
    ans=0
    for y in range(n):
        for x in range(n):
            #현위치(y,x)에 놓였을 때 수명을 구한다.
            ans=max(ans, maxAge(y,x))
    print(ans)

---

[실패 코드1 - Pypy3 - 시간초과]

- 각 원소별로 최대 수명을 구한다.

- BFS를 이용했다.

- 다음위치의 값(대나무개수)이 현위치의 값보다 크면 큐에 계속 추가하며, 나이를 더한다.

import sys
from collections import deque
input = sys.stdin.readline
q=deque()

#상하좌우
dy=(-1,1,0,0)
dx=(0,0,-1,1)

def bfs(y,x):
    global MAP, n
    max_age=0
    q.append((y,x,1))
    visited=[[False]*n for _ in range(n)]
    
    while q:
        cury, curx, age=q.popleft()
        max_age=max(max_age, age)
        for i in range(4):
            nexty=cury+dy[i]
            nextx=curx+dx[i]

            #다음위치가 n행 n열 배열의 원소에 속하는가?
            if (nexty>=0 and nexty<n) and (nextx>=0 and nextx<n):
                #다음위치가 처음값보다 더 크고, 아직 방문하지 않았는가?
                if (MAP[nexty][nextx]>MAP[cury][curx]) and (not visited[nexty][nextx]):
                    q.append((nexty, nextx, age+1))
    return max_age
        

n=int(input().strip())
MAP=[ [*map(int,input().strip().split())] for _ in range(n)]
dp=[[0]*n for _ in range(n)]
max_age=0
for y in range(n):
    for x in range(n):
        dp[y][x]=bfs(y,x)
        max_age=max(max_age, dp[y][x])
        
print(max_age)

 

[참고]

https://yabmoons.tistory.com/154

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