1520번: 내리막 길 / gold 3 / DP, DFS
https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
- 시간초과
'''
1520번: 내리막 길 / gold 3 /
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0
def dfs(x, y):
global cnt
if x == n - 1 and y == m - 1:
cnt += 1
else:
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] < graph[x][y]:
dfs(nx, ny)
# 1. n, m , graph 입력 받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
# 2. (0,0) 출발 -> (n-1, m-1) 도착 개수 찾기
dfs(0, 0)
print(cnt)
- 정답
'''
1520번: 내리막 길 / gold 3 / DP, DFS
'''
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
def dfs(x, y):
# 목적지 도착시 -> 이동했던 칸들 1씩 더하기
if x == n - 1 and y == m - 1:
return 1
# 아직 이동하지 않은 칸에 왔을 시, 상하좌우 탐색하기
if dp[x][y] == -1:
dp[x][y] = 0
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] < graph[x][y]:
dp[x][y] += dfs(nx, ny)
return dp[x][y]
# 1. n, m, graph 입력 받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
# 2. dp 리스트 만들기
dp = [[-1 for _ in range(m)] for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
# 3. DFS + DP 활용
print(dfs(0, 0))코드 리뷰
- 처음에 짠 코드는 DFS 알고리즘을 사용해서 내리막길 갯수를 구한 코드이지만, 시간 초과가 발생했습니다.
- 시간을 단축시키는 방법들을 고민하다 구글링을 해서 해결 방법을 알게 되었습니다.
- 처음 짠 DFS알고리즘을 활용한 코드는 / 이미 탐색한 곳을 다시 탐색 할 수 있으므로 시간초과가 발생합니다.
- 따라서 이미 탐색한 곳을 다시 탐색하지 않게끔 DP를 활용하는 것이 문제 핵심입니다.
- 해당 문제의 예시 그림을 보면, 32 는 -> 20 또는 30 방향 선택지가 있습니다.
- 처음에 DFS 알고리즘을 통해 [ ... -> 32 -> 20 -> 17 -> 15 -> 10] 도착지 까지 도달하게 됩니다.
- 도착지에 도달했기에, 해당 경로들은 dp 값이 1씩 증가하게 됩니다.
- 그 다음, 백트래킹으로 인해 [ ... -> 32 -> 30] 이 선택되고, DFS 로 [ ... -> 32 -> 30 -> 25 -> 20] 경로가 움직입니다.
- 20의 값을 가진 해당 위치의 dp 값은, 처음 DFS로 도착지까지 도달해서 얻은 1의 값이 있으므로
- 그 이후의 도착지 까지 가는 경로 [ 20 -> 17 -> 15 -> 10] 를 생략할 수 있습니다.
