Baekjoon 1937. 욕심쟁이 판다 / Python

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

알고리즘 설명

문제 설명

주어진 n * n 크기의 대나무 숲에서 판다가 최대로 많은 칸을 이동할 수 있는 경로를 찾는 문제

1. 상, 하, 좌, 우 로만 이동할 수 있다.
2. 현재 칸에 있던 대나무보다 더 많은 대나무가 있는 칸으로만 갈 수 있다.

풀이 설명

알고리즘

DFS, DP : 각 칸에서 이동 가능한 모든 경로를 탐색하고, 이미 계산된 경로라면 DP를 활용한다.

시간 복잡도

최악의 경우 O(n ** 2)의 시간 복잡도를 가진다. n < 500 이므로 충분.

from collections import deque as dq
import sys; input = sys.stdin.readline
sys.setrecursionlimit(250000)


n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]

# 이동 방향 설정: 하, 우, 상, 좌
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# DFS와 메모이제이션을 사용하여 최대 이동 칸 수를 계산하는 함수
def dfs(x, y):
    if dp[x][y]:  # 이미 계산된 경우 메모이제이션 결과 반환
        return dp[x][y]
    
    dp[x][y] = 1  # 초기값 설정: 최소 1칸 이동 가능
    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > arr[x][y]:
            dp[x][y] = max(dp[x][y], 1 + dfs(nx, ny))
    
    return dp[x][y]

# 각 칸을 시작점으로 DFS를 실행하여 최대 이동 칸 수를 계산
for i in range(n):
    for j in range(n):
        if not dp[i][j]:
            dfs(i, j)

# 최대 이동 칸 수 출력
print(max(map(max, dp)))