어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다.
이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다.
우선 고수들의 예시를 보자
위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다.
그렇다면 DP배열은 아래와 같이 설정된다.
그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다.
그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다.
그러면 이미 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를 더 풀어보아야 겠다.
'알고리즘' 카테고리의 다른 글
[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드) (0) | 2021.07.26 |
---|---|
[python3] 백준 1967 풀이 (트리의 지름, DFS) (0) | 2021.07.26 |
[py3] 백준 2573 풀이 (빙산, DFS, 그래프) (0) | 2021.07.24 |
[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법) (0) | 2021.07.22 |
백준 1202 보석도둑 c++ 풀이 (priority queue, vector, 우선순위 큐) (0) | 2021.07.21 |