[백준] 1937번 욕심쟁이 판다 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/1937

문제해결 아이디어

• 상, 하, 좌, 우로 이동해서 최대 일수를 구한다는 것에서 dfs를 바로 떠올릴 수 있었다.
• 경로를 반복해서 이동하는 문제를 줄이기 위해 dp를 사용하였다.
• dfs와 dp를 사용하는 것이 핵심인듯 하다.

소스코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

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

dp = [[0] * n for _ in range(n)]


def dfs(x, y):
    if dp[x][y]:  # 이미 들린 경로라면
        return dp[x][y]

    dp[x][y] = 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] > graph[x][y]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)

    return dp[x][y]


ans = 0

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

print(ans)