[백준/1520/파이썬] 내리막 길

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

1520번: 내리막 길

Problem

• 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다.
• 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
• 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

조건

• 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다.
• 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

SOL

경로를 찾는 문제이다. 

• 경로를 찾는 문제는 보통 , DFS/BFS를 사용하는데, BFS/DFS로 이 문제를 구현하라고 했다면, O(4^NM)이겠지만, 이 문제는 조건에 따라서, 안가도 될 곳이 분명하다.
• 따라서, DFS로 구현하되,조건만 걸어주면, 연산횟수가 매우매우 줄어든다.

  이때, 최적화에 사용되는 방법이 바로 메모이제이션이다. 따라서, 이 문제는 DP +DFS 를 합친 문제라고 볼 수 있다.

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

N,M = map(int,input().split())
maps=[list(map(int,input().split())) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
dy=(0,1,0,-1)
dx=(1,0,-1,0)
def moving(y,x):
    if y==N-1 and x==M-1:
        return 1
    if visited[y][x] !=-1:
        return visited[y][x]
    visited[y][x] =0
    for k in range(4):
        ny=y+dy[k]
        nx=x+dx[k]
        if 0<=ny<N and 0<=nx<M:
            if maps[ny][nx]<maps[y][x]:
                visited[y][x] +=moving(ny,nx)
    return visited[y][x]


print(moving(0,0))