난 DFS보다 BFS를 더 선호한다. 하지만 BFS로 풀기 어려운 탐색 문제들이 꽤 있다.
이 문제도 그런 문제 중 하나.

BOJ 1520 - 내리막 길 링크
(2022.10.06 기준 G3)
(치팅하면 앞으로 오르막길만 걷게 됨)

문제

칸마다 높이가 써져 있는 세로 크기 M, 가로 크기 N의 지도가 있고 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 가려고 한다. 이 때, 높이가 더 낮은 지점으로만 이동하여 목표 지점으로 가고자 한다면, 가능한 경로 수를 출력

알고리즘

간선의 가중치가 없으므로 (전부 동일하므로), BFS나 DFS를 사용해야 한다. 하지만, 이 문제는 Top-Down 방식의 DP + DFS를 사용해야 한다. 이유는 풀이에서 후술.

풀이

이런 문제는 기본적으로 모든 경로를 일일이 찾아가면 거의 무조건 시간 초과가 난다.
그러므로 DP를 사용한 탐색을 사용해야 한다. 여기서 두 가지 방법이 있다.
1. Top-Down (재귀)
2. Bottom-UP (반복문)
이 문제는 Bottom-Up은 힘들 것이다. Bottom-Up은 단순하게 상향하면서 답을 구하는 방식이지만, 이 문제는 사방 중 높이가 낮은 지점으로 이동이 가능하다. 즉, 구불구불하게 이동할 수 있으므로 코드 짜기가 좀 많이 힘들어진다.
하지만 재귀를 이용한 Top-Down은 간단하다. 출발점으로부터 도착점까지 쭉 파고들고 도착점에 도착하면 들려온 모든 경로에 1을 증가시키고 방문한 칸에는 결과를 저장(메모이제이션)을 해놓으면 된다. 그러면 앞으로 불필요한 중복되는 탐색은 하지 않게 되는 것이다.
Top-Down은 앞으로도 정말 많이 나오는 알고리즘 기법이다. 외판원 순회의 틀이라고도 할 수 있는데, 잘 알아두자.

주의사항

메모이제이션을 위해 DP 배열을 만들 때에는 꼭 -1로 초기화하자.
0으로 초기화하면 안된다.

코드

import sys; input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(m, n):
    if m == M - 1 and n == N - 1: # 목적지에 도착했으면
        return 1 # 경로가 되므로 1 반환
    if dp[m][n] > -1: # 방문한 적이 있는 위치이면
        return dp[m][n] # 저장되어 있는 경로의 수 반환
    dp[m][n] = 0
    for mm, nn in [(m - 1, n), (m + 1, n), (m, n - 1), (m, n + 1)]: # 상하좌우
        if 0 <= mm < M and 0 <= nn < N and matrix[m][n] > matrix[mm][nn]: # 범위 안이고 다음 위치의 높이가 더 낮아야 한다.
            dp[m][n] += dfs(mm, nn) # 다음 위치를 dfs하여 결과를 더한다.
    return dp[m][n]

M, N = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(M)] # 지도
dp = [[-1] * N for _ in range(M)] # 각 위치마다 메모이제이션
print(dfs(0, 0))

여담

개인적으론 Top-Down과 Bottom-Up을 정확하게 몰랐다. 그냥 느낌대로 풀어왔는데, 이 풀이를 쓰기 위해 좀 찾아보고 했는데, 공부가 좀 된 것 같다.