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

문제

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

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

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

 

기록

(dp 14일차) 지도 관련 dp 문제는 확실히 재귀로 구현하는 쪽이 훨씬 쉬운 것 같다. 결과 중 시간초과에서 조금 당황했었는데, dp 배열을 0으로 초기화 해놔서 '목적지로 가는 경우의 수가 없다(=0)'를 저장했을 때 탈출조건에서 걸리지 않아 시간초과가 나온 것 같다. 그래서 -1로 초기화했더니 성공! 

 

이번 문제는 재귀로 구현했는데, 자신보다 작은 상하좌우 칸으로 이동하는 재귀함수를 사용했다. dp[i][j]에는 (i, j)에서 목적지로 가는 경우의 수를 저장하여, 재귀함수 실행 중 같은 칸을 호출했을 때 저장해놓은 경우의 수를 반환한다.

 

코드

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

n, m = map(int, input().split())
board = [list(map(int, input().split())) for i in range(n)]
dp = [[-1]*m for i in range(n)]

def go(y, x):
    # base case
    if y==n-1 and x==m-1 : return 1
    if dp[y][x]!=-1 : return dp[y][x]
    # step
    count = 0
    if y>0 and board[y][x]>board[y-1][x]: count+=go(y-1, x)
    if y<n-1 and board[y][x]>board[y+1][x]: count+=go(y+1, x)
    if x>0 and board[y][x]>board[y][x-1]: count+=go(y, x-1)
    if x<m-1 and board[y][x]>board[y][x+1]: count+=go(y, x+1)
    dp[y][x] = count
    return dp[y][x]

print(go(0, 0))

1. 재귀함수를 사용하기 때문에 setrecursionlimit을 해준다.

2. 입력된 값 저장하고, (i, j)에서 목적지로 가는 경우의 수를 저장할 이차원 dp 배열 생성

3. 자신보다 작은 상하좌우 칸으로 이동하며, 현재 칸에서 목적지로 가는 경우의 수 반환하는 재귀함수 go 구현

- base case : 목적지면 1 반환, dp 배열에 저장된 함수 값이면 해당 값 반환

- step : 상하좌우 칸의 경우의 수를 모두 더하여 현재 칸의 경우의 수로 저장

4. 위의 재귀함수 사용하여 (0, 0) 칸에서 목적지로 가는 경우의 수 출력