[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP)

어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다.

이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다.

 

우선 고수들의 예시를 보자

위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다.

2->8까지 이동한다면 (0,0)은 7값을 갖는다.

그렇다면 DP배열은 아래와 같이 설정된다.

그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다.

그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다.

1이 이동가능한 방향은 2와 8이다.

그러면 이미 DP(0,0)은 최댓값을 가지고 있으므로 2의 값을 가져와서 1을 추가한다면 DFS없이 최대 일 수를 구할 수 있다. 그렇다면 DP(1,0)은 8이 되면 되는 것이다.

 

그렇다면 우선 필요한 것은 두개다

1. DFS가 필요하다. 단, 지나온 좌표에 최댓값을 설정해주어야 하므로 재귀를 활용한 DFS가 필요하다.

2. DP가 필요하다. 만약 해당 좌표의 DP값이 존재하면 값을 반환하고 값이 없다면 DFS를 하도록 만든다.

 

import sys
input = sys.stdin.readline

from sys import setrecursionlimit 
setrecursionlimit(10**9)

n = int(input())
M = []
for i in range(n):
    tmp = list(map(int, input().split()))
    M.append(tmp)
dp = [[0 for i in range(n)] for i in range(n)]

dy = [0, 0, 1, -1]  # 동서남북
dx = [1, -1, 0, 0]  # 동서남북
def DFS(y, x):
    if dp[y][x] != 0:
        return dp[y][x]
    dp[y][x] = 1
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if (0 <=ny<n) and (0<=nx<n) and M[ny][nx] > M[y][x]:
            dp[y][x] = max(dp[y][x], DFS(ny,nx)+1)
    return dp[y][x]

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

코드에서 어려웠던 부분은 재귀 DFS였다. 재귀로 DFS를 짜본적이 거의 없었기 때문에 상당히 감을 잡기 어려웠고, 일단 원리부터 파악하는게 힘들었다. DP를 더 풀어보아야 겠다.