B)1520

내리막길

문제

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

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

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

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

DFS + DP(Dynamic Programming)

사실 분할/정복 문제라고 판단되고, DP를 사용해야겠다는 생각까진 크게 오래 걸리지 않았지만,,
구현과 DFS를 함께 사용하는 부분, 그리고 시간 관련 까지 고민을 꽤 오래 한 문제이다.

구현
1.dp는 초기 값을 -1로 설정한 2차원 배열로 둔다.(visited 같은 역할)
2.Top-down(DP) + Recursion(DFS) 방식을 사용하기 때문에 (n-1, m-1)부터 거꾸로 (0, 0)까지 간다.
3.만약 dp 값이 -1이라면(방문되지 않았다면), 0으로 만들고 동,서,남,북을 탐색하여 높은 칸이 있을 때 dfs를 사용한다, 그리고 그 재귀 결과를 dp값에 더해준다.
4.만약 dp 값이 -1이 아니라면, 이미 방문이 되었다는 뜻이므로 dp값을 그대로 return한다.

코드를 보기 전, 재귀함수를 구현할 시 가장 중요한 것 먼저 짚고 가도록 하겠다.

sys.setrecursionlimit(10**8)  #재귀 구현할 때 필수적인 문장.

파이썬에선 생각보다 얕은 깊이의 재귀(스택)을 제공한다.
따라서 많은 양의 재귀(Recursion)을 요구하는 코딩 문제에선 필수적으로 사용해야하는 문장이다.
진짜 런타임 에러가 계속 떠서 열받았다..

코드를 살펴보자

import sys
sys.setrecursionlimit(10**8)  #재귀 구현할 때 필수적인 문장.
input = sys.stdin.readline
m, n = map(int, sys.stdin.readline().split())
matrix = []
for _ in range(m):
    matrix.append(list(map(int, sys.stdin.readline().split())))


dx = [0, +1, 0, -1] #동서남북
dy = [+1, 0, -1, 0]
dp = [[-1]*n for _ in range(m)] #visited 개념으로 사용하였다.
dp[0][0] = 1
def dfs(x, y):
    global matrix
    global dp
    step = matrix[x][y] #현재 위치
    if x == 0 and y == 0:
        return 1
    if dp[x][y] == -1:      #0으로 시작하면, 많이 겹치게됨
        dp[x][y] += 1
        for i in range(4):  #4방향 탐색
            a, b = x + dx[i], y + dy[i] #a,b 현재 탐색중인 x,y 좌표
            if 0 <= a < m and 0 <= b < n:
                temp = matrix[a][b]
                if temp > step:    # 더 낮은 계단칸
                    dp[x][y] += dfs(a, b)
    return dp[x][y]


result = dfs(m-1, n-1) #거꾸로 실행 목표 지점 부터 시작지점까지.
print(result)

진짜 푸는데 오래걸렸다. DP 알고리즘을 어떤 때에 사용하면 좋은지 정도만 기억나고 구현을 어떻게 해야하는지 도저히 기억이 나질 않았다. 결국 구글링과 지난 강의자료들까지 참고하면서 겨우겨우 구현해낸 것 같다.
나름대로 열심히 하고는 있는데, 아직 파이썬이 미숙한 언어인 부분과, 몇년의 공백을 채우기엔
역부족이란 생각이 들었다.