[백준] 1937. 욕심쟁이 판다

문제

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

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

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

입력

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

출력

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

입력 예시

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

출력 예시

4

풀이

메모이제이션과 dfs를 이용해서 푸는 문제이다.

n의 범위가 1부터 500까지이기 때문에 단순히 bfs 혹은 dfs만 사용할 경우 아래 첨부 사진과 같이 "시간초과"가 발생할 것이다.

(아래는 bfs로만 풀고 위에는 dfs로만 풀고 시간초과가 난 것이다..ㅎㅎ)

기존에 dfs나 bfs를 풀 때 시간초과 혹은 메모리초과 등의 런타임에러를 방지하기 위해 사용하던 "방문체크 2차원 배열"을 사용하는 것이 "키포인트"라고 생각한다.

# RecursionError를 방지하기 위해 (백준 파이썬 체점 서버는 재귀깊이한계가 1000이다. n이 500까지이고 500*500까지 갈까봐 작성하였다)
import sys
sys.setrecursionlimit(10**6)

# 입력
# 대나무 숲의 크기 n, 대나무 숲의 정보 fr
n = int(input())
fr = [list(map(int, input().split())) for i in range(n)]

# **중요**
# 해당 지점에 풀어놓았을 때 판다가 최대 살 수 있는 일수를 memo하는 2차원 배열 (메모이제이션)
# 판다는 무조건 최대 하루는 살기 때문에 1로 초기화하였다
max_live = [[1] * n for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
	# 최대 살 수 있는 일수가 1을 넘으면 바로 리턴해준다
    if max_live[x][y] != 1:
        return max_live[x][y]
  
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if -1 < nx < n and -1 < ny < n:
            if fr[x][y] < fr[nx][ny]:
            	# 상하좌우를 다 보는데, 예를 들어 '상'으로 이동하는 게 가장 최댓값을 볼 수 있다고 할 때 '하', '좌', '우'에서의 값들은 무시해야함
                # 아래와 같이 max(max_live[x][y], dfs(nx, ny) + 1)을 해줌으로써 상하좌우 이동 후 최댓값을 max_live[x][y]에 저장할 수 있음
                 max_live[x][y] = max(max_live[x][y], dfs(nx, ny) + 1)

    return max_live[x][y]

answer = 0
for i in range(n):
    for j in range(n):
        answer = max(answer, dfs(i, j))

print(answer)

처음 이 문제를 풀려고 하는데, 잘 안풀려서 dfs를 두 문제 정도 풀고 재도전했다. 메모이제이션 부분은 여전히 어려워 일부 구글의 힘을 빌렸다. dfs + dp 문제를 여러 개 풀어봐야겠다.