[ 백준 / 1520 ] 내리막길 (Python)

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

 

난이도 : 골드 3 
알고리즘 유형 : DFS, DP 
풀이 시간 : 33분 

문제 풀이 

$(0, 0)$ 부터 $(N - 1, M - 1)$까지 가기 위한 경우의 수를 구하자. 단, 이동 시에는 이전 높이보다 항상 낮은 곳으로만 이동해야 한다.

 

문제의 조건을 살펴본다면, $N, M ≤ 500$으로 주어졌고, 상하좌우로 이동이 가능하기 때문에, 모든 경우에 대해 살펴본다면 $O(4^{500})$으로 시간초과가 나게 된다. 따라서 우리는 DP 테이블을 활용하여 이전에 왔던 경우의수에 대해서 저장해주어야 한다.

 

먼저 grid 상에서 이동은 dfs 알고리즘을 사용해 진행하였다. 기본적인 틀은 4방향에 대해 탐색하면서, 현재 위치보다 새로운 위치가 낮은 경우, 이동해보는 과정이다. 또한, 한 지점에서 몇 번의 이동이 가능한지 경우를 체크하기 위해 `tmp`변수를 이용하여 카운트를 진행해주었다.

def dfs(r, c):
    tmp = 0
    for d in range(len(dr)):
        nr, nc = r + dr[d], c + dc[d]
        if 0 <= nr < n and 0 <= nc < m and grid[r][c] > grid[nr][nc]:
            tmp += dfs(nr, nc)
    return tmp

이 방법이 기본적인 시간초과가 나는 dfs 풀이법이다. 우리는 이 틀에서 최적화를 진행해줄 것이다.

 

먼저, dp테이블을 적용하기 위해 전체 경우의 수인 `tmp`를 `dp[r][c]`에 저장해주었고, 이 값을 return 시켜주었다.

또한, 종료지점에 다다른 경우, 경우의 수를 카운트해야하기 때문에 `1`을 리턴해주었다.

마지막으로, 현재 지점에서 경우의 수 계산이 한 번이라도 된 경우에는, `dp[r][c]`를 리턴해주었다.

 

여기서 주의해야 할 점이 있다.

만약 dp 테이블의 초기값을 `0`으로 설정해준 경우, 현재 위치에서 경로가 애초에 없는 녀석들을 처리할 때, 중복되어 탐색이 진행될 것이다. 따라서, 이를 방지하기 위해 dp 테이블을 `0`이 아닌 `-1`로 초기화해주어 dfs를 이어간다면, 한번도 간 적이 없는 경우(`dp[r][c] = 0`)에 대해 메모이제이션을 진행할 수 있게 된다.

 

코드

'''
상하좌우 인접한 곳이 있음
항상 높이가 더 낮은 지점으로만 이동하여 목표지점까지 가고자 한다.

2차원 그래프에서 낮은 지점으로 이동하기 위한 경우의수를 구하기
'''

import sys
sys.setrecursionlimit(10**7)

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def dfs(r, c):
    # 모든 지점에서 계산이 한번이라도 된다면, 재사용
    if dp[r][c] != -1:
        return dp[r][c]
    # 종료지점에 다다른 경우, 1 리턴
    if (r, c) == (n - 1, m - 1):
        return 1
    # 한 점에서 다른 지점으로 이동이 몇 번 가능한지에 대한 합을 리턴해줘야함
    tmp = 0
    for d in range(len(dr)):
        nr, nc = r + dr[d], c + dc[d]
        if 0 <= nr < n and 0 <= nc < m and grid[r][c] > grid[nr][nc]:
            tmp += dfs(nr, nc)
    dp[r][c] = tmp
    return dp[r][c]


n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

# 만약 dp의 초기값을 0으로 설정한다면, 경로가 애초에 없는 녀석들 같은 경우, 계속해서 탐색을 이어갈 것이다.
# 따라서, 0이 아닌 -1로 초기화를 해주면 해결가능하다.
dp = [[-1] * m for _ in range(n)]

dfs(0, 0)

print(dp[0][0])

배운 점 

2차원 배열에서의 dp를 사용하기 위해 강의를 수강하였는데, 확실히 접근법을 이해하는데 도움이 되었던 것 같다. 1년 전에는 dp를 이해하지 못한 상태에서 풀어나갔는데, 1년 뒤 풀어보니 확실히 로직의 흐름을 이해하고 푸는 데 있어 큰 차이가 존재하는 것 같다ㅎㅎ !