문제

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

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

www.acmicpc.net/problem/1937

  • 입력

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

  • 출력

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

최종코드

안그래도 어려운 dfs에 dp까지 합쳐서 구현하려니까 너무 어려웠다. dfs를 하면서 dp 값을 저장해놨다가, 이미 dp 값이 있는 칸이면 dfs를 멈추고 dp 값을 이용하면 된다.

import sys
sys.setrecursionlimit(100000)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dfs(sx, sy):
    global n, dp, arr
    dp[sx][sy] = 1

    # 상하좌우 네 방향 탐색
    for i in range(4):
        x = sx + dx[i]
        y = sy + dy[i]
        # index가 범위 안이며 이전 값보다 이동할 칸의 값이 더 큰 경우
        if 0 <= x < n and 0 <= y < n and arr[sx][sy] < arr[x][y]:
            # 방문하지 않은 칸이면 dfs를 계속 진행
            if dp[x][y] == 0:
                dp[sx][sy] = max(dp[sx][sy], dfs(x, y) + 1)
            # 이미 방문한 칸이라면 dp 값을 이용
            else:
                dp[sx][sy] = max(dp[sx][sy], dp[x][y] + 1)

    return dp[sx][sy]

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
res = 0
for i in range(n):
    for j in range(n):
        if dp[i][j] == 0:
            res = max(res, dfs(i, j))

print(res)

참고 사이트