[백준] 1937 : 욕심쟁이 판다 - Python

문제

보드에서 경로 찾기 문제.
단순한 DFS로는 시간 초과가 발생하게 만든 문제이다.
-> DP(동적 프로그래밍)를 결합하여 효율성을 높여야 하는 문제

내 코드

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

sys.stdin = open("input.txt", "rt")

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

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


def isInner(x, y):
    return 0 <= x < n and 0 <= y < n


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


# dp[x][y]는 (x,y)에서 시작했을 때 최댓값
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 not isInner(nx,ny): continue

        if g[nx][ny] > g[x][y]: # 이동 가능
            dp[x][y] = max(dp[x][y], DFS(nx,ny) + 1)

    return dp[x][y]

res = 0
for i in range(n):
    for j in range(n):
        res = max(res, DFS(i,j))

print(res)

코멘트

처음에 DP를 생각하질 못했다. 그냥 모든 지점에서 계속 상하좌우 탐색하면서 문제를 풀어봤는데, 시간초과가 발생

DFS + DP 결합으로 문제 풀기
dp[x][y] = max(dp[x][y], DFS(nx,ny) + 1) 의 부분을 완벽하게 이해하는 것이 중요했다.

현재 위치에서의 최대 경로 = max(인접한 큰 값 위치에서의 최대 경로) + 1

단순 DFS로 접근하면 모든 지점에서 시작하여 상하좌우 계속 탐색하는 방식. -> 단순 DFS는 중복 계산이 많아 비효율적이라는 것을 깨달았고, 같은 위치를 여러 번 방문하게 되면서 불필요한 연산이 발생한다.

DP를 결합하면 (메모이제이션) 중복 계산을 피할 수 있다. 각 위치에서 최대 이동 거리를 메모이제이션하면 효율적이다.

DFS(x,y)는 (x,y)에서 시작해서 가능한 최대 경로수잖아.
그렇기에 dp[x][y] = max(dp[x][y], DFS(nx,ny) + 1) 이 되는 이유도

결국은 (x,y) -> (nx,ny)로 이동 가능한데 DFS(nx,ny) 역시 (nx,ny)에서 시작했을 때의 최대 경로 수이고 (x,y)는 (nx,ny)로 이동 가능하므로 + 1을 한 것과 같다.

코드의 핵심 부분

def dfs(x, y):
    if dp[x][y]:  # 이미 계산된 결과가 있다면 그 값을 반환
        return dp[x][y]
    
    dp[x][y] = 1  # 현재 위치에서의 최소 이동 횟수
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if isInner(nx, ny) and g[nx][ny] > g[x][y]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)
    
    return dp[x][y]

1. 메모이제이션 확인 : 이미 계산된 결과가 있으면 바로 반환
2. 초기값 설정 : 현재 위치만 포함하므로 1로 초기화
3. 상하좌우 탐색 : 조건에 맞는 방향으로 DFS 수행
4. 최대값 갱신 : 각 방향의 결과 중 최대값 선택
5. 결과 반환 : 계산된 최대 이동거리 반환