BOJ 1937(욕심쟁이 판다)풀이

solved.ac 티어 : 골드 3

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

어느 한 위치를 선택했을 때 그 위치에서 최대로 갈 수 있는 개수를 저장하고 dfs를 돌면 된다.

최대 개수 구하는 방법은 한쪽으로 쭉 내려가고 더이상 내려갈 수 없을 때부터 +1씩 해주면 된다.

 

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
a=int(input())
l=[list(map(int,input().split()))for i in range(a)]
ch=[[0 for i in range(a)]for g in range(a)]
dy=[-1,0,1,0]
dx=[0,1,0,-1]
def dfs(y,x):
    if ch[y][x]!=0:return ch[y][x]
    s=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or nx>=a or ny<0 or ny>=a:
            continue
        if l[ny][nx]>l[y][x]:
            s=max(s,dfs(ny,nx)+1)
    ch[y][x]=s
    return s
ma=0
for i in range(a):
    for g in range(a):
        if ch[i][g]==0:
            dfs(i,g)
            #for ii in range(a):
            #    for gg in range(a):
            #        print(ch[ii][gg],end=" ")
            #    print()
            #print()

        ma=max(ma,ch[i][g])
print(ma)