[백준] 1520_내리막 길 (DFS & DP 이용)

📕 문제

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

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

 

 

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

 

[입력]

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

 

[출력]

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

 

💡 풀이법

1. dp를 이용하지 않으면 시간초과가 난다...

2. 지도와 같은 사이즈의 2차 행렬인 dp를 만든다.

(여기에서 dp에 저장되는 수는 각 위치에서 도착지까지 갈 수 있는 경우의 수가 담김)

3. 해당 위치가 dp리스트에서 -1이면 아직 방문하지 않은 위치이기 때문에 탐색을 시작한다.

4. 그 위치에서 사방을 확인하며 지도상에서 더 낮은 방향이 있다면 그 위치에 대해서 다시 dfs를 실행한다.

(이때, 다음 위치에서의 dfs의 반환값을 현재 위치의 dp에 저장한다)

5. dfs를 돌면서 도착지에 도착하면 1을 반환한다.

4. 만약 도착도 안했고, 방문을 했던 위치라면 dp에는 그 곳에는 그 위치에서 도착지까지 갈 수 있는 경우의 수가 담겨 있을 것이기 때문에 그 수를 반환한다.

 

import sys
sys.setrecursionlimit(10000)

dxy = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(n):
    x, y = n
    if x == M-1 and y == N-1: 
        return 1
    if dp[x][y] == -1:
        dp[x][y] = 0
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            if -1 < nx < M and -1 < ny < N:
                if matrix[nx][ny] < matrix[x][y]:
                    dp[x][y] += dfs((nx, ny))
    return dp[x][y]

            
M, N = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
dp = [[-1 for _ in range(N)] for _ in range(M)]
print(dfs((0,0)))