188. 1520(내리막 길) - 파이썬

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

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

travleMap = [list(map(int, input().split())) for _ in range(M)]
dp = [[-1] * N for _ in range(M)]


def dfs(x, y):
    # 도착지점
    if x == M-1 and y == N-1:
        return 1

    # -1이면 방문하지 않았다는 것임.
    if dp[x][y] == -1:

	# 목적지까지 갈 수 없는 경우는 0으로 반환
        dp[x][y] = 0

        # dx, dy 는 현재 기준 상하좌우
        for dx, dy in (1, 0), (-1, 0), (0, -1), (0, 1):
            if 0 <= x+dx < M and 0 <= y+dy < N:
                if travleMap[x+dx][y+dy] < travleMap[x][y]:
                    dp[x][y] += dfs(x+dx, y+dy)
    return dp[x][y]


print(dfs(0, 0))

문제요약

(0,0)에서 마지막 지점까지 가는데 상하좌우로 값이 더 작은 쪽으로 이동하라.

설명

이 문제는 깊이우선 탐색(DFS)과 동적계획법(DP) 개념을 사용해야 풀 수 있다.

깊이우선 탐색으로는 해당 분기에서 모든 노드를 비교하여 완벽하게 탐색후 다음으로 넘어 갈 것이다.

그러면 모든 노트 탐색으로 인해 시간초과가 발생할 것이다.

 

따라서 하나의 큰 문제를 작은 단위로 만들어 풀어줌(dp)과 동시에 방문을 계산을 했음을 알려주면서 연산 횟수를 줄여준다.

먼저 빨간색 부분은 출발부분, 초록색 부분은 도착부분이다.

 

도착지점(초록색)은 x와 y좌표가 M-1, N-1일 것이다.

따라서 도착지점은

    # 도착지점
    if x == M-1 and y == N-1:
        return 1

로 알려준다.

 

그리고 우리는 위에서 말한것처럼 dp를 통해서 방문여부도 확인할 것이다.

따라서 -1로 방문하지 않은 경로임을 알려주자.

dp = [[-1] * N for _ in range(M)]

 

dp가 -1이라는 것은 방문하지 않았다는 뜻이다.

연산이 정상적으로 실행된다.

일단 해당 경로가 목적지까지 갈 수 없는 경로일 수 있다. (상하좌우에 자신보다 낮은 값이 없을경우)

그 경우를 위해 처음에 0을 선언하고 실제로 목적지까지 도달이 불가능하면 0을 반환할 것이다. 

    # -1이면 방문하지 않았다는 것임.
    if dp[x][y] == -1:

        # 방문했음을 알림
        dp[x][y] = 0

 

그럼 이제 초기 셋팅은 끝났고 상하좌우를 실제롤 비교해야한다.

자신 기준 +(1,0)은 상  +(-1,0)은 하  +(0,-1)은 좌  +(0,1)은 우 이다.

상하좌우 값이 M,N의 범위를 벗어나지 않는다면 첫번째 조건에 만족한다.

두번째로는 상하좌우(x+dx,y+dy)가 자신(x,y)보다 작으면  앞으로 나아간다.

        # dx, dy 는 현재 기준 상하좌우
        for dx, dy in (1, 0), (-1, 0), (0, -1), (0, 1):
            if 0 <= x+dx < M and 0 <= y+dy < N:
                if travleMap[x+dx][y+dy] < travleMap[x][y]:
                    dp[x][y] += dfs(x+dx, y+dy)

 

이런식으로 목적지(도착지점)에 도달한 경우에는 계속 +1이 되어 우리가 구하고자 하는 최종 결과를 도출해 낼 수 있다.