BOJ - 내리막 길(1520)

골드4 : dp & DFS 문제이다.

풀이

이게.. 접근 방식을 약간 반대로해서 오래걸렸다. 바텀 업 방식으로 사고를 하여, 마지막 지점까지 가는데 있어 4방향의 경로를 더해주어야 한다고 생각했다. 그런데 그렇게 생각을 하니 쉽게 점화식이 떠오르지 않았다.

이럴 때는 일단 기본적인 골자인 그래프 방법의 해결방식부터 출발하는 것이 좋다. 즉, 일단 이 문제는 DFS 탐색 문제라 생각하면 편하다. 그러나 250000 크기의 판이고, 그냥 할 경우 당연히 시간초과가 날 것이다.

그럼 일단 기본적인 DFS는 어떤 방식인가? 특정 위치에서 다음 위치를 구하고, DFS를 다시 돌리는 방식이다. 여기서 힌트를 얻어야 한다. 해당 위치에서의 경로는 다음 위치에서 구한 경로들의 합으로 구성된다. 그렇기 때문에 이러한 DFS적 풀이 방법에 dp를 적용하는 것이 수월한 풀이를 할 수 있다.

그 다음은 쉽다. dp 를 적용하여, 이미 방문한 위치인 경우는 더해주는 것으로 추가적인 연산을 줄일 수 있다. 기억하자.

그리고 setrecursionlimit은 함수다…

Code

import sys
from pprint import pprint
 
sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline
 
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1 for _ in range(m)] for _ in range(n)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
 
# dp[i][j] = 4방향에서 발생하는 가능한 경로의 합(단, graph[i][j] > graph의 다음 경로 : 즉, 가능한 경로)
 
 
def DFS(y, x):
    dp[y][x] = 0  # 해당 함수의 호출 이유는, 해당 지점으로 부터 경로를 구하라는 것임 : 경로 개수는 0개일 수 있음
    if y == n - 1 and x == m - 1:  # 경로를 구하라고 했는데 도착지점이면 경로를 1로 업데이트 해줌
        dp[y][x] = 1
        return dp[y][x]
 
    for dy, dx in d:
        ny, nx = y + dy, x + dx
        if 0 <= ny < n and 0 <= nx < m and graph[y][x] > graph[ny][nx]:
            if dp[ny][nx] == -1:  # 아직 방문하지 않았다면,
                dp[ny][nx] = DFS(ny, nx)
            dp[y][x] += dp[ny][nx]  # 이미 방문해서 탐색을 완료했다면, 그대로 더해줌
    return dp[y][x]
 
print(DFS(0, 0))

Reference

• 백준(1520번) - 내리막 길