[다이나믹 프로그래밍] ★ 1520번 - 내리막 길

[백준] 1520번 - 내리막 길

(한줄평) 오랜만에 dp 문제플 풀었더니 약간 헤맸던 문제다. dp와 dfs를 한 번에 쓰는 문제는 처음이라 낯설었던 것 같기도 하다. 꼭 복습이 필요한 문제!

풀이 시간: 60분 이내

 

1) 문제 해결 아이디어

n * m의 지도의 높이 정보가 주어지고 지금보다 높이가 더 낮은 곳으로만  이동하여 (0, 0)에서 (n-1, m-1)까지 이동 가능한 경로의 수를 구하는 문제다. 

이 문제는 DFS + DP 를 이용하여 풀 수 있는 문제다.

오로지 DFS로만 풀려고 한다면 가능한 모든 경로의 수를 다 세야하기 때문에 아마 시간초과가 날 것이다. n, m의 범위가 1이상 500이하이기 때문이다. 

 

DFS와 DP를 이용하여 풀어야한다는 것은 알았는데 점화식을 잘못세워서 헤맸다.

처음에 나는 d[i][j]를 (i, j)에서 (n-1, m-1)까지 이동 가능한 경우의 수라고 세우지않고

d[i][j]를 (0, 0)에서 (n-1, m-1)까지 이동가능한 경우의 수라고 하고 문제를 풀었는데 내 생각대로 잘 해결되지 않았다. 

 

<dfs 동작과정>

1. 도착점이면 경우의 수를 1개 리턴

2. (x, y)에서 도착점까지 가는 경우의 수를 이미 구했다면 바로 값을 리턴

이미 구했다면 굳이 다시 구할 필요가 없음!!

3. (x, y)에서 도착점가지 가는 경우의 수를 아직 구하지 않았다면 방문처리를 함(경우의 수를 0으로 초기화)

4. 상하좌우 탐색

4-1. 탐색할 좌표가 범위 내이고 탐색할 곳(graph[nx][ny])이 현재지점(graph[x][y])보다 더 낮은 곳이라면 이동

5. (x, y)에서 도착점까지 가는 경우의 수 리턴

 

예제 입력의 동작 과정을 확인하려면 아래 접은글을 참고하자.

[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]

[0, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[-1, -1, -1, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 0, -1, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 0, 0, -1, -1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 0, 0, 0, -1]

[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, -1]

[1, 0, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, -1, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 0, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 0, -1]
[1, -1, -1, 0, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 0, -1]
[1, -1, -1, 0, -1]
[1, -1, -1, 0, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 1, -1]
[1, -1, -1, 1, -1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 1, 0]
[1, -1, -1, 1, -1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, -1]

[1, 0, 0, 1, 0]
[1, -1, -1, 1, 0]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, -1]

3
[3, 2, 2, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, -1]

 

 

첫번째 오류. 런타임 에러(RecursionError)

최대 재귀 깊이를 정해주지 않아서 생긴 오류이다. 보통은 sys.setrecursionlimit(10**6) 로 해주면 해결이 된다.

 

<점화식>

2) 소스코드

import sys
sys.setrecursionlimit(10**6)  # 최대 재귀 깊이 설정
input = sys.stdin.readline

def dfs(x, y):
  '''
  # dp 기록 과정 확인 
  for i in d:
    print(i)
  print()
  '''
  # 도착점이면 경우의 수 1개 리턴
  if x == n - 1 and y == m - 1:
    return 1
  # (x, y)에서 도착점까지 가는 경우의 수를 이미 구했으면
  if d[x][y] != -1:
    return d[x][y]  # 바로 리턴
  # (x, y)에서 도착점까지 가는 경우의 수를 아직 구하지 않았으면
  d[x][y] = 0  # 방문 처리(경우의 수를 0으로 초기화)
  
  # 상하좌우 탐색
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    # 탐색할 좌표가 범위내 이면
    if 0 <= nx < n and 0 <= ny < m:
      # 탐색할 지점이 현재 지점보다 더 낮은 곳이면 이동
      if graph[nx][ny] < graph[x][y]:
        d[x][y] += dfs(nx, ny)  
  return d[x][y]

n, m = map(int, input().split())  # 세로, 가로
# n * m 의 높이 정보
graph = [list(map(int, input().split())) for _ in range(n)]
# (i, j)에서 출발해서 (n-1, m-1)까지 가는 경우의 수
d = [[-1] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(dfs(0, 0))  # 이동 가능한 경로의 수

[참고] https://studyandwrite.tistory.com/387

[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP