[백준] 1937번 : 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

깊이우선탐색(DFS)와 메모리제이션 으로 문제를 해결 하였습니다.

 

깊이우선탐색 선택 이유 : 현재의 위치에서 다음위치로 갈 수 있는 경로가 있을때, 그 다음위치의 최대값 + 1 한 값이 현재위치이기 때문에 좀더 코드적으로 보기 편하다.

 

한번 탐색한 경로는 이미 최대의 크기를 가지고 있기때문에 탐색할 필요가 없어 메모리에 저장해두어 탐색하지않고 값을 리턴한다.

 

import sys
sys.setrecursionlimit(400000)
move = ((0,1), (0,-1), (1,0) , (-1,0))
n = int(input())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
    

def dfs(i,j, visited):
    if visited[i][j]:
        return visited[i][j] + 1
    
    maxvalue = 1
    for dy, dx in move:
        ny = i + dy
        nx = j + dx
        if n > ny >=0 and n > nx >= 0: 
            if graph[ny][nx] > graph[i][j]: #  # 이미 방문한곳이 아니고 현재위치보다 먹이가 많다면
                if visited[ny][nx]:
                    distance = visited[ny][nx] + 1
                else:
                    distance = dfs(ny, nx, visited) + 1
                maxvalue = max(distance, maxvalue)
    
    visited[i][j] = maxvalue
    return visited[i][j]
        

visited = [[0 for _ in range(n)] for _ in range(n)]
maxvalue = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            distance = dfs(i,j, visited)
            maxvalue = max(distance, maxvalue)
            
            
print(maxvalue)

주의해야할 사항은 깊이우선탐색을 할때에는 반드시 sys.recursionlimit 값을 설정해주어야한다.

참고로 pypy에서는 sys.recursionlimit 값이 동작되지 않는다.

 

재귀 문제를 풀때에는 Python 으로 제출하는것을 권장합니다.