[BOJ][🟡3][백준#01937] 욕심쟁이 판다

문제 출처

BAEKJOON Online Judge #1937

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

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

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

예제

입력

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

출력

4

My Sol

import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline

def check_around(i, j):
    global dp, N, visit
    if dp[i][j]: return dp[i][j]
    visit[i][j] = 1

    cur, flag = 0, 0
    for di, dj in ((-1,0),(1,0),(0,1),(0,-1)):
        si, sj = i+di, j+dj
        if not (0<=si<N and 0<=sj<N): continue
        if mat[i][j] >= mat[si][sj]: continue
        if dp[si][sj]:
            flag = 1
            if cur < dp[si][sj]:
                cur = dp[si][sj]
            continue

        if visit[si][sj]: continue

        check_cnt = check_around(si, sj)
        if check_cnt: flag = 1
        if cur < check_cnt:
            cur = check_cnt
    dp[i][j] = cur+1 if (cur or flag) else -1
    return dp[i][j]

N = int(input())
mat = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*N for _ in range(N)]
visit = [[0]*N for _ in range(N)]

maxx = 0
for i in range(N):
    for j in range(N):
        ret = check_around(i, j)
        if maxx < ret:
            maxx = ret

print(maxx+1)

DP를 활용해 푸는 문제였다. 주변에 갈 수 있는 경로의 크기를 저장하는 DP 2차원 배열을 DFS를 이용해 채워넣고 조회하는 방식으로 문제를 푼다.

1. 입력을 처리한다.
2. 모든 좌표에 대해 완전탐색을 실시한다. dp 배열에 해당 좌표가 값을 가지고 있는지 조회하는 것
3. 만약 dp 배열에 해당 좌표의 값이 없다면 주변을 탐색해서 가능한 경로의 수+1을 해주어야 한다. 만약 주변에 이동이 불가능하다면 -1을 dp에 채워넣는다.
4. 재귀와 DP를 사용해서 사실상 상하좌우 주변을 한 번씩만 조회해서 현재 좌표에서의 dp값을 결정한다.
5. 전체 dp 배열에서 가장 큰 값을 완전탐색 중에 maxx에 기록하여 maxx+1 을 출력한다.

결과

맞았습니다!!