[백준/1520] 내리막 길 (Python)

Problem : https://www.acmicpc.net/problem/1520

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:06:07

 

---

 

문제 설명

 

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 

 

입력 및 출력

 

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

입력 예시

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

출력 예시

3

 

 

---

 

풀이

 

DP, 그 중에서도 메모이제이션을 중점적으로 이용한 문제.

• 목적지, 즉 DP[M-1][N-1]의 값은 1로 초기화한다(도착지에 도착할 때 경우의 수 한 가지를 반환하기 위함이다)
• 우리가 임의의 좌표 x, y에 접근할때, 다음 두 가지가 가능하다.
  • DP에 이미 값이 채워져 있을때, 즉 DP[y][x]에 값이 존재할 때는 그 값을 바로 반환한다.
  • DP에 값이 없을 땐, DP[y][x]를 0으로 초기화하고, 4방향으로 탐색을 시작한다. 만약 조건에 맞다면(상하좌우의 값이 현재 좌표의 값보다 작다면) 탐색을 이어나갈 수 있고, 재귀적으로 계산한 경우의 수를 더한다. 최종적으로 업데이트된 DP[y][x]를 반환한다.
  • 이를 0, 0 좌표에서부터 탐색한다면 최종적으로 DP[0][0]에 모든 경우의 수가 저장된다.

 

풀이 코드

import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

M, N = map(int, input().split())
map_list = [list(map(int, input().split())) for _ in range(M)]

dp = [[-1]*N for _ in range(M)]
dp[-1][-1] = 1

def dfs(x, y):
  if dp[y][x] > -1 :
    return dp[y][x]

  dp[y][x] = 0
  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < N and -1 < ay < M and map_list[y][x] > map_list[ay][ax] :
      dp[y][x] += dfs(ax, ay)

  return dp[y][x]

print(dfs(0, 0))

풀이 완료~