https://www.acmicpc.net/problem/1520
1520번: 내리막 길
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.
www.acmicpc.net
📌 - 처음 접근한 방법
- 내리막이 나올때마다 그 칸의 값을 다음 내리막 칸의 값에 더해준다
- 모든 경로를 전부 탐색해서 마지막 칸의 값을 출력
이렇게 브루트포스로 풀었었는데, 바로 메모리 초과가 났다
📌 - 두번째 접근 방법
시간초과와 메모리초과를 동시에 해결하려면 DFS만으로는 풀 수가 없다.
DFS나 BFS를 사용하면서 DP개념을 활용해야 이 문제를 해결 할 수 있다.
- DFS로 경로의 끝까지 탐색하면서 해당경로를 방문체크한다.
- 끝점에 다다랐을 때 DFS를 사용한 방향만큼 +를 해서 해당 경로로 갈 수 있는 경우의 수를 찾는다
- 첫 지점까지 도달했을 때의 값을 출력한다.
처음에 이해를 잘못해서 DFS로 그냥 처음부터 체크하는거랑 DP를 사용하는 거랑 뭐가 다른지 이해하지 못했다.
DFS와 DP를 같이 쓰는 이유는 DFS로 방문한 경로를 다른 경로로 다시 가게 되었을 때, 이미 방문한 경로부터 도착점까지 가는 경로를 단축시켜 준다는 것이다.
글로 설명하기에 이해하기 복잡해서 그림으로 보자면
해당 그림에서 32 -> 30, 32 -> 20 으로 2방향으로 갈 수 있는데,
DFS로 전부 체크를 하게 되면 20 -> 17 -> 15 -> 10 의 작업을 겹친 경로만큼 반복하게 되서 시간초과가 나게 된다.
DP로 처음 32 -> 10으로 가는 경로에서 방문 체크를 하고 다시 32 -> 30 -> 25 일때 25에서는 이미 20은 -1이 아니기 때문에 dp[x][y]를 리턴하고 dfs를 종료하게 되므로 해당하는 만큼 경로 소모를 줄일 수 있다.
🔥 - python 코드
from sys import stdin as s
s = open('input.txt','rt')
N ,M = map(int,s.readline().split())
arr = [list(map(int,s.readline().split())) for _ in range(N)]
dp = [[-1] * M for _ in range(N)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x,y):
if x == N-1 and y == M-1:
return 1
if dp[x][y] != -1:
return dp[x][y]
dp[x][y] = 0
for z in range(4):
nx = x+ dx[z]
ny = y + dy[z]
if 0<= nx < N and 0<= ny <M:
if arr[nx][ny] < arr[x][y]:
dp[x][y] += dfs(nx,ny)
return dp[x][y]
print(dfs(0,0))
