[BOJ]1937. 욕심쟁이 판다

문제:

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 잇따. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력:

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

풀이방법:

 기본적으로는 dfs를 사용해서 판다의 이동 경로를 알아야 하지만 문제에서 원하는 것은 판다가 최대한 살 수 있는 일수, 즉 최대로 이동 가능한 거리의 길이를 원하고 있다. 작은 크기의 경우에는 시작점을 달리 해서 최대 일수를 찾을 수 있지만 500 x 500의 경우에는 이 것을 다 탐색하기에는 많은 시간이 걸릴 것이다.

 따라서 이를 해결하기 위해서 다이나믹 프로그래밍에서 메모리제이션을 사용한다. 한 점에서 출발을 해서 움직이다가 이미 이전에 다른 곳에서 움직였던 기록이 남아있고 그것을 기록해뒀다면 더 이상 그 길로 이동할 필요없이 그 값을 참조해서 다시 돌아오면 된다. 따라서 dfs로 이동을 하지만 이전에 이 길을 지나간 기록이 있다면 그 값을 가져오고, 그렇지 않다면 더 들어가면서 값을 기록하도록 한다.

 또한 재귀적으로 함수를 구현했기 때문에 깊은 재귀로 인한 에러를 방지하기 위해서 sys.setrecursionlimit를 사용한다.

import sys
sys.setrecursionlimit(1000000)
 
def dfs(x,y):
    global answer
    
    if dp[x][y] != 0:
        return dp[x][y]
 
    dp[x][y] = 1
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx< n and 0 <= ny< n:
            if trees[nx][ny] > trees[x][y]:
                dp[x][y] = max(dp[x][y], dfs(nx, ny)+1)
    return dp[x][y]
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
n = int(input())
trees = []
for _ in range(n):
    trees.append(list(map(int, input().split())))
 
answer = 0
visited = [[0 for _ in range(n) ] for _ in range(n)]
dp = [[0 for _ in range(n) ] for _ in range(n)]
 
for i in range(n):
    for j in range(n):
        answer = max(dfs(i,j),answer)
print(answer)

문제링크:

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

1937번: 욕심쟁이 판다