[백준 01520] 내리막 길 [Java]

문제

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

---

풀이

최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.

단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.

중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.

DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수

우선 입력을 받자.

모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.

dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.

그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y]를 0으로 초기화해주자.

4개의 방향에 대해 유효한 범위이고, 문제의 조건대로 이전 위치보다 값이 작은 경우에만 탐색을 진행해주자.

이때, 위에서 도착지에 도달했거나 이미 방문한 지역이라면 dp값을 반환하는데 해당 값을 더해주면 된다.

이러한 과정이 반복된다면 모든 경로에 대한 경우의 수가 맨 처음 탐색을 시작한 (0, 0)으로 반환되며, dp[0][0]을 출력하면 된다.

---

소스코드

보기