백준 1520 내리막 길

문제 풀이

dp와 dfs를 함께 사용해야하는 문제이다.

1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.

2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.

  2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.

  2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.

  2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.

 

Python Code

import sys
sys.setrecursionlimit(10000)
# 0: 상, 1: 좌, 2: 하, 3: 우
a = [0,-1,0,1]
b = [-1,0,1,0]
def dfs(x,y):
    if dp[y][x] == -1 : 
        dp[y][x] = 0
    if x<0 or x>n-1 or y<0 or y>m-1: return 0
    for i in range(4):
        nx = x + a[i]
        ny = y + b[i]
        if (0 <= nx <= n-1 and 0 <= ny <= m-1) and maps[ny][nx] > maps[y][x] :
            if dp[ny][nx] > 0:
                dp[y][x] += dp[ny][nx]
            # 방문한 적 없으면 dfs
            elif dp[ny][nx] == -1 :
                dp[y][x] += dfs(nx,ny)
    return dp[y][x]
        
if __name__ == '__main__':
    m,n = map(int,sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
 
    dp = [[-1] * n for _ in range(m)]
    dp[0][0] = 1
    dfs(n-1,m-1) 
    print(dp[-1][-1])
 

Line 9 : 지도를 벗어나면 0을 반환한다.

Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).

 

문제 링크

1520번: 내리막 길