[백준] 1520 파이썬(python) : 내리막 길 - dp+dfs

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

1520번: 내리막 길

 

 

dp는 목적지에서부터 뒤로 가는 패턴

 

(0, 0)에서 (m-1, n-1)까지 가는 방법의 수를 구하는 문제인데 (m-2, n-1)에서 (m-1, n-1)까지 1가지 방법 밖에 없으니 dp[m-2, n-1]에는 1을 추가하는 방식으로 되돌아가면서 결국 dp[0][0]에 저장되는 값이 도착지점까지의 갈 수 있는 방법이 된다.

 

import sys
m, n = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(m) ]
dp = [ [-1]*n for _ in range(m) ]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]

def dp_bruteForce(x, y):
    if x == m-1 and y == n-1: #1
        return 1
    if dp[x][y] != -1: #2
        return dp[x][y]
    dp[x][y] = 0 #3
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if graph[nx][ny] < graph[x][y]: #4
                dp[x][y] += dp_bruteForce(nx, ny) #5
    return dp[x][y] #6

print(dp_bruteForce(0, 0))

 

#1 : 처음에 끝까지 탐색해서 도착지점에 가면 도착지점 값을 1로 리턴

#2 : 이미 방문한 곳이면 그 값을 반환

#3 : 방문처리 후에 뒤로가는 과정에서 값을 추가해줌

#4 : 내리막길이므로 새로운 지점의 값이 기존 지점의 값보다 작아야 한다.

#5 : 재귀호출을 4개 방향으로 해주어서 해당위치의 dp값을 계속 추가

#6 : 4개 방향을 모두 돌아 탐색이 끝나면 dp[x][y]값 리턴해서 부모 노드의 4개 방향 탐색 중 하나 완료

 

dp + dfs문제였는데 dp를 그래프이론에도 적용할 수 있는게 신기했다. 완전탐색으로 4가지 방향까지 탐색하면 시간 초과가 날텐데 dp를 이용해서 불필요한 계산을 줄이니 통과할 수 있었다.