[백준/BOJ] gold4 - 1520번 내리막 길 (Python)

▶1520 - 내리막 길

▶문제

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

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

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

 

▶입력

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

 

▶출력

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

 

▶예제

 

▶풀이

dp + dfs 활용하는 문제이다.

단순히 dp만 이용하면 풀 수 있는 문제가 아니라 거기다가 dfs를 넣어서 경로별로 최대 값을 설정해 주어야한다.

 

이문제는 말로 설명하는 것보다 코드를 보면 바로 이해가 될 것이다.

import sys
sys.setrecursionlimit(10**6)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(x, y):
    if x == m-1 and y == n-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]

    dp[x][y] = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if 0 <= nx < m and 0 <= ny < n:
            if arr[nx][ny] < arr[x][y]:
                dp[x][y] += dfs(nx, ny)
    return dp[x][y]


m, n = map(int, input().split())
arr = []
for i in range(m):
    arr.append(list(map(int, input().split())))

dp = [[-1 for _ in range(n)] for _ in range(m)]
print(dfs(0, 0))

처음에 제출했을 때는 RecursionError가 떴다.

재귀를 하는 동안에 백준 python에서 제공하는 횟수를 초과해서 뜨는 런타임 에러이다.

import sys
sys.setrecursionlimit(10**6)

앞에 이 코드 두줄만 넣어주면 RecursionError가 뜨지 않을 것이다.

드디어 플래티넘까지 100점 남았다.

아직은 갈길이 멀지만 하루하루 꾸준히 문제를 풀다 보면 이번 방학 때는 플래티넘을 찍을 수 있을 거 같다.