[BOJ] 1520 내리막길 python

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

1520번: 내리막 길

문제

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

예시 1

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

qk

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

입력

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

출력

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

 

해설

사용하는 알고리즘: DFS, Dynamic Programming

 

1. 현재 위치(here)로 부터 상하좌우로 움직였을 때(there) 지도에 표시된 값이 현재 값보다 작으면 함수를 재귀적으로 수행

2. 1번 방식으로 탐색을 하다. 마지막 지점(M-1, N-1) 에 도착하면 1을 반환 한다.

3. 반환 된 값은 현재 위치의 경로에 더해준다.

 

식으로 써보면

 

현재 위치의 내리막길 경로 수  = 현재 위치에서 조건에 맞게 상하좌우로 이동했을 때  새로운 위치에서 내리막길 경로의 수의 합

 

자세한 내용은 코드를 보면서 설명하도록 하겠다.

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

M, N = map(int, input().split())

MAP = []

#num_routes[row][col]은 row, col에서 부터 목적지까지 내리막 길으로만 갈 수 있는 방법의 수 
num_routes = [[-1 for i in range(N)] for i in range(M)]

#입력
for _ in range(M):
    row = list(map(int, input().split()))
    MAP.append(row)
    

moves= [(1,0,),(-1,0,),(0,1,),(0,-1)]

#위치를 입력으로 받음
def dfs(here):

	#만약 현재 위치가 목적지라면 1 반환
    if here == (M-1, N-1):
        return 1
	
    row, col = here
    
    #현재 위치가 이미 방문한 곳이라면 저장해둔 값을 반환
    if num_routes[row][col] != -1:
        return num_routes[row][col]
    
    num_routes[row][col] = 0
    #상하좌우로 움직임
    for drow, dcol in moves:
        nrow = row + drow
        ncol = col + dcol
    	
        #범위에서 벗어난다면 제외
        if nrow >= M or nrow < 0 or ncol >= N or ncol <0:
            continue
		
        #내리막 길이라면
        if MAP[row][col] > MAP[nrow][ncol]:
        	#현재위치(here)부터 목적지까지 도착하는 방법의 수를 업데이트
            #dfs((nrow, ncol,))은 새로운 위치에서 목적지까지 내리막길 경로 수를 반환한다.
            #이 함수의 마지막 줄을 보면 알 수 있다.
            num_routes[row][col] += dfs((nrow, ncol,))
	
    #현재위치에서 목적지까지 도달하는 방법의 수를 반환
    return num_routes[row][col]

print(dfs((0,0,)))