백준 1937번 - 욕심쟁이 판다

욕심쟁이 판다 문제 바로 가기

풀이 날짜: 2026-01-09

baekjoon 알고리즘 문제 풀이

풀이 코드


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

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

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

def dfs(x,y):
    if dp[x][y] != 0:
        return dp[x][y]
    dp[x][y] = 1

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0<=nx<n and 0<=ny<n and graph[nx][ny] > graph[x][y]:
            dp[x][y] = max(dp[x][y], 1+dfs(nx,ny))
    return dp[x][y]

answer = 0

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

print(answer)

문제 핵심 요약:

욕심쟁이 판다는 (0,0)에서 출발하는 문제가 아니라, 어떤 칸에서 시작하든 상관없이, 판다가 더 많은 대나무가 있는 칸으로만 이동하며 “최대로 살아남을 수 있는 이동 칸 수”를 구하는 문제이다. 여기에서 중요한 점은, 같거나 작은 칸으로는 이동하지 못하고, 더 큰 값으로만 간다는 점이다. 결국 이 문제는 최단거리/최소비용 같은 최적화가 아니라, 증가하는 경로 중 최장 길이를 찾는 문제로 해석해야 했다.

처음에 잘못 잡은 풀이 방향

처음에는 “어차피 큰 값으로만 가니까, 최솟값부터 시작해서 BFS로 퍼지면 되지 않을까”라고 생각했다. 그래서 visited를 만들어서 최소값 칸을 찾아 방문 표시하고 BFS를 시도하려고 했다. 하지만 이 문제는 한 번 방문하면 끝나는 탐색 문제가 아니었다. 따라서 visited로 막아버리면 오히려 정답 경로를 막는 구조가 되어, 시작점을 최소값 하나로 고정하는 것은 틀린 방향이었다.

DFS + DP(메모이제이션)

각 칸에서 더 큰 값으로만 이동하므로 경로는 항상 증가 방향이다. 즉 재귀로 ‘최대로 뻗는 길이’를 계산하면 된다. 단 모든 칸에서 DFS를 하면 중복 계산이 발생하기 때문에, 이미 계산한 칸의 결과를 dp에 저장해두고 재사용하는 ‘메모이제이션’이 필요했다.

DP 정의

-dp[x][y] = (x, y) 칸에서 시작했을 때 판다가 최대로 살아남는 일수

현재 칸 (x, y)의 값이 graph[x][y]라면, 4방향 이웃 (nx, ny) 중에서 graph[nx][ny] > graph[x][y]인 칸으로만 이동할 수 있다.
이때 갈 수 있는 칸이 하나도 없다면 그 칸에서 더 이상 못 움직이므로 최소 1일은 산다.

이동 불가 → dp[x][y] = 1
이동 가능 → dp[x][y] = 1 + max(dfs(nx, ny))

구현 과정에서 겪은 어려움

왜 visited가 아니라 dp인지

visited는 “한 번 갔으면 다시 안 감”이라는 의미인데, 이 문제는 그래프 탐색이 아니라 최장 경로 계산이다. 방문 여부보다 “그 칸에서 시작했을 때 최대 길이”라는 값이 필요하고, 그 값이 바로 dp에 저장된다. 즉, 이 문제에서 dp는 단순 배열이 아니라 캐시(메모이제이션) 역할까지 동시에 수행한다.

런타임 에러(재귀 깊이) 이슈와 해결

DFS를 재귀로 구현하면, 최악의 경우 경로 길이가 매우 길어져 파이썬 기본 재귀 제한(약 1000)을 넘을 수 있다.
따라서 sys.setrecursionlimit(10**7)를 추가해줬다.

Vienna sausage