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

✏️ 문제

1937번: 욕심쟁이 판다

✏️ 풀이

이 문제는 딱봐도 DFS문제로 보이지만 단순하게 DFS + 완전탐색으로 풀이하면 시간초과가 난다.

경로와 관련해서 고민하다보면 최소 경로를 불필요하게 중복해서 탐색함을 알 수 있다.

따라서 해당 좌표에서의 최소 경로에 대해 Memorization이 필요하다. 

따라서 일반적인 DFS로 풀이하되, 이미 해당 좌표에 대해 최소 경로가 구해져있다면 바로 return하도록 한다.

✏️ 코드

import sys
sys.setrecursionlimit(10**6)
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
path = [[0] * N for _ in range(N)]
day = 0

def is_valid(x, y):
    return 0 <= x < N and 0 <= y < N

def dfs(x, y):
    global count
    if path[x][y] != 0:
        return path[x][y]

    path[x][y] = 1
    for n in range(4):
        nx, ny = x + dx[n], y + dy[n]
        # 큰 곳으로만 이동할 수 있음
        if is_valid(nx, ny) and arr[nx][ny] > arr[x][y]:
            path[x][y] = max(path[x][y], dfs(nx, ny) + 1)

    return path[x][y]

for x in range(N):
    for y in range(N):
        day = max(day, dfs(x, y))

print(day)

갔던 곳을 다시 방문하는 경우, 이미 path 배열이 채워져있어 바로 return 되므로 방문여부를 저장하는 배열은 따로 사용하지 않았다.