b1520. 내리막길

 

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

 

 

 DFS와 메모이제이션을 활용하여 격자에서 시작점에서 도착점까지 내리막길만 따라가는 경로의 개수를 계산하는 문제다.
입력으로 주어진 N×M 크기의 격자는 각 칸에 고도 값이 저장되어 있으며, 이동은 인접한 칸으로만 가능하고 반드시 현재 위치보다 고도가 낮은 곳으로만 갈 수 있다.

프로그램은 먼저 dpdpdp라는 메모이제이션 배열을 -1로 초기화한다.

이는 특정 위치에서 출발해 도착점까지 갈 수 있는 경로의 개수를 저장하는 역할을 한다.

그리고 value라는 2차원 배열에 고도 정보를 저장한다.

dir 배열은 상하좌우 네 방향으로 이동하기 위한 도구로 사용된다.

DFS는 시작점에서 출발해 가능한 모든 경로를 탐색한다.

경로를 탐색하는 도중, 만약 이미 dp[x][y] 값이 계산되어 있다면 저장된 값을 재사용한다.

이는 중복 계산을 방지해 프로그램의 효율성을 높인다.

 

재귀적으로 호출되는 DFS는 현재 위치에서 도착점에 도달할 수 있는 모든 경로의 개수를 누적하며, 최종적으로 시작점에서 호출된 DFS는 전체 가능한 경로의 총합을 반환한다.

이 프로그램의 핵심은 내리막길이라는 조건을 활용해 탐색 범위를 줄이고, 메모이제이션을 통해 이미 계산한 값을 재활용함으로써 중복 계산을 제거한다는 점이다.

dp[x][y]는 특정 위치에서 출발한 경우의 경로 개수를 저장하므로,

재귀 호출이 중복되지 않도록 한다.