[골드 3] 백준 1937 - 욕심쟁이 판다 (파이썬)

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

풀이

• N×N 크기의 숲이 있다.
• 각 칸에는 대나무가 자라고 있고, 숫자는 대나무의 양이다.
• 판다는 현재 위치보다 더 많은 양의 대나무가 있는 칸으로만 이동할 수 있다.
• 상하좌우로 이동 가능하다.
• 판다는 최대한 많은 날을 살아야 하므로, 이동할 수 있는 경로 중 가장 긴 경로의 길이를 구해야 한다.

풀이 아이디어

• 특정 위치 (r, c)에서 시작해 이동할 수 있는 최대 경로를 구한다.
• 이미 계산한 값은 cache[r][c]에 저장해 중복 호출을 방지한다 (메모이제이션).
• 결국 각 칸에서 출발했을 때의 최대 이동일수 중 최댓값이 정답이다.

N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]

F는 숲의 정보를 담는 2차원 리스트이다.

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

dr, dc는 트릭으로 상하좌우 이동을 위한 방향 벡터를 나타낸다.

cache = [[-1] * N for _ in range(N)]

cache[r][c]는 (r, c)위치에서 시작해 이동할 수 있는 최대 일수를 저장한다.

def dp(r, c):
    if cache[r][c] != -1:
        return cache[r][c]

이미 방문한 위치면, 저장된 결과를 그대로 반환한다.

    ret = 1
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if nr < 0 or N <= nr or nc < 0 or N <= nc:
            continue
        if F[r][c] < F[nr][nc]:
            ret = max(ret, 1 + dp(nr, nc))

상하좌우를 탐색하면서, 자신보다 대나무 양이 더 많은 곳으로 이동할 수 있는지 확인하고, 이동 가능한 곳 중에서 최장 경로를 찾는다.

    cache[r][c] = ret
    return ret

현재 위치에서 최대 이동 가능한 날짜 수를 저장하고 반환한다.

print(max([dp(r, c) for r in range(N) for c in range(N)]))

모든 좌표에서 출발하는 경우를 고려해 가장 긴 이동거리를 출력한다.

코드

# 백준 1937 - 욕심쟁이 판다
# 분류 : 다이나믹 프로그래밍

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

cache = [[-1] * N for _ in range(N)]
def dp(r, c) :
    if cache[r][c] != -1 :
        return cache[r][c]
    
    ret = 1
    for i in range(4) :
        nr, nc = r + dr[i], c + dc[i]

        if nr < 0 or N <= nr or nc < 0 or N <= nc :
            continue

        if F[r][c] < F[nr][nc] :
            ret = max(ret, 1 + dp(nr, nc))

    cache[r][c] = ret    
    return ret

print(max([dp(r, c) for r in range(N) for c in range(N)]))