[백준] 1520번: 내리막 길 (python)

1520번:  내리막 길

---

문제 )

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

 

 

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

 

 

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

풀이)

평소처럼 DFS를 이용해 문제를 풀어보면

예제는 정답이 잘 나오는데 제출시에 메모리 초과나, 시간 초과가 나오게 된다.

이 이유는 각 지점의 높이나 깊이가 너무 깊어지기 때문이다. 이를 해결하기 위해서는 DP를 활용하여 이 문제를 

풀어주어야 한다.

 

DP에는 해당 인덱스에서 [n, m]까지 갈 수 있는 경우의 수를 담아주게 된다.

 

import sys
sys.setrecursionlimit(1 << 20)
 
def dfs(a, b):
    di = [-1, 0, 0, 1]
    dj = [0, -1, 1, 0]
 
    # 목적지에 도착했을 시 1 return
    if a == n - 1 and b == m - 1:
        return 1
 
    # 비교 값
    me = g[a][b]
    for i in range(4):
        x = a + di[i]
        y = b + dj[i]
        if -1 < x < n and -1 < y < m and g[x][y] < me:
            # 이미 방문한 곳인 경우 처리
            if visited[a][b]:
                return dp[a][b]
            dp[a][b] += dfs(x, y)
 
    # 4방향이 탐색이 모두 끝나면 방문처리
    visited[a][b] = 1
 
    # 모든 탐색이 끝난 후 결과 리턴
    return dp[a][b]
 
 
n, m = map(int, sys.stdin.readline().strip().split())
g = [list(map(int, sys.stdin.readline().strip().split())) for i in range(n)]
visited = [[0] * m for i in range(n)]
dp = [[0] * m for i in range(n)]
 
print(dfs(0, 0))

---

출처 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길