[Python] 백준 1937. 욕심쟁이판다 (DP)

문제 링크

문제 풀이

• 전체적 흐름:

  어떤 지점에 처음 풀어 놓아야 하는지 모르기 때문에
  모든 칸을 시작으로 하여 dfs 탐색해봄
  이때, 특정 칸을 시작으로 dfs 탐색한 이후, 그 칸에서 최대로 이동한 칸의 개수가 cnt보다 크면 업데이트함.
  그렇게 해서 가장 많이 이동한 칸의 개수를 저장한 cnt를 마지막으로 출력
  

• dfs 원리:

  이 문제에서는 dfs를 모든 칸에 대하여 해야 하는데,
  이렇게 되면 반복적으로 탐색하는 칸이 존재할 것이며 이로 인해 비효율성과 시간초과를 발생시킬 수 있음
  그래서 dfs에 dp를 적용해야 함.
  • dp[x][y]는 (x, y) 좌표에서 시작했을 때 최대한 이동할 수 있는 칸의 개수를 저장하도록 설정.
    dfs(x, y)는 dp[x][y]를 구하고, 그 값을 반환하는 함수.
  • dfs(x, y)에서 다음 칸에 대해 탐색 할 때 (그래프 범위 내에 있고, 다음 칸의 대나무 양이 현재 칸의 것보다 큰 경우의 칸에 한해서),
    • 다음 칸(n_x, n_y)에 대한 기록인 dp[n_x][n_y] 값을 이용하여 dp[x][y]를 구함. -> 1 + dp[n_x][n_y]
    • dp[n_x][n_y] 값이 없으면 dfs(n_x, n_y)를 재귀적으로 호출하여 dp[n_x][n_y]를 먼저 구한 후 dp[x][y]를 구함. -> 1 + dfs(n_x, n_y)
      
  • 이때, (x, y)을 시작으로 하는 경로가 여러가지일 수 있기에,
    여러 경로 중 방문 칸 수가 최대인 값으로 dp[x][y]를 설정하기 위해
    그동안의 값들을 temp라는 변수를 이용해 업데이트하다가,
    temp 최댓값을 dp[x][y]에 저장.
  • 이후 dp[x][y]를 반환

코드

import sys

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

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


def dfs(x, y):
    temp = 1
    for i, j in zip(dx, dy):
        n_x, n_y = x + i, y + j
        if 0 <= n_x < n and 0 <= n_y < n:
            if graph[n_x][n_y] > graph[x][y]:
                if dp[n_x][n_y] != -1:
                    temp = max(temp, 1 + dp[n_x][n_y])
                else:
                    temp = max(temp, 1 + dfs(n_x, n_y))
    dp[x][y] = temp
    return dp[x][y]


if __name__ == '__main__':
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)]
    dp = [[-1] * n for _ in range(n)]

    cnt = 0
    for x in range(n):
        for y in range(n):
            cnt = max(cnt, dfs(x, y))
    print(cnt)