[BOJ/백준] 1937 욕심쟁이 판다

# 1937 욕심쟁이 판다 실패(Fail)
def dfs(x,y):
    global N
    stack = [(x,y,0)]
    last_direction = []
    while stack:
        cx,cy,distance = stack.pop()
        flag = True
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx<N and 0<=ny<N:
                if bamboo[cx][cy] < bamboo[nx][ny]:
                    if dp[nx][ny] == -1:
                        stack.append((nx,ny,distance+1))
                    else:
                        if distance + dp[nx][ny] + 1 > dp[x][y]:
                            dp[x][y] = dp[nx][ny] + distance + 1
                           
                    flag = False
        if flag:
            if dp[x][y] < distance + 1:
                dp[x][y] = distance + 1
 
 
 
N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
 
result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)
print(max(map(max,dp)))

이 문제를 단순하게 DFS로 풀면 시간 초과가 날수 밖에 없다. 왜냐하면 입력이 최대가 500*500 이므로, dp를 통해 이미 탐색한 값들을 저장해놓는 과정이 필요하다. 위의 코드는 시간초과가 난 코드이다. 

dp를 사용하긴 했지만, 각 (x,y) 축에서 dfs를 하지만, 이 이동경로에 있는 좌표들에 대해서 이미 한번 측정한 값인데, 다시 한번 dp를 측정해야하는 것이다.

 

 

import sys
 
 
def dfs(x,y):
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if bamboo[nx][ny]>bamboo[x][y]:
                    distance = dfs(nx,ny) + 1
                    dp[x][y] = max(distance,dp[x][y])
        return dp[x][y]
 
 
 
 
 
 
 
N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)
 
print(max(map(max,dp)))

재귀를 이용한, 이동 경로에 대해서 전부 한번에 업데이트를 해주는 것이다.

 

최초 이동경로에서 (x0,y0) = > (x1,y1) => (x2,y2) => ...=>(xn,yn) 각 경로마다 최대로 갈수 있는 이동경로들을 저장해준다. 그리고 return된 값에 + 1을 해줘 해당 칸에 갔을때의 이동거리를 측정해주고, 최대값을 갱신해주면 된다.

 

이렇게 하면 장점은 어느 곳에서 한번 방문했던 곳은 더 이상 dfs를 하지않고 해당 위치에서의 최대값을 반환해주는 것이다.

 

이 문제는 각 위치마다의 최대경로를 구하는 로직과, 그걸 이용해서 시간복잡도를 줄이는게 중요한 문제였다.