# 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를 하지않고 해당 위치에서의 최대값을 반환해주는 것이다.
이 문제는 각 위치마다의 최대경로를 구하는 로직과, 그걸 이용해서 시간복잡도를 줄이는게 중요한 문제였다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 14503 로봇 청소기 (0) | 2021.02.16 |
|---|---|
| [BOJ/백준] 16946 벽 부수고 이동하기 4 (0) | 2021.02.16 |
| [BOJ/백준] 9466 텀 프로젝트 (0) | 2021.02.15 |
| [BOJ/백준] 1759 암호 만들기 (0) | 2021.02.15 |
| [BOJ/백준] 1991 트리 순회 (0) | 2021.02.15 |