문제
M×N 크기의 지도에서 (0, 0)에서 (M-1, N-1)까지 이동하는 경로의 수를 구한다. 이동은 상하좌우 4방향이며, 반드시 현재 위치보다 낮은 곳으로만 이동할 수 있다.
입력
첫째 줄에 M과 N이 주어진다. (1 ≤ M, N ≤ 500) 이후 M줄에 걸쳐 각 칸의 높이 값이 주어진다. (0 ≤ 높이 ≤ 10,000)
출력
(0, 0)에서 (M-1, N-1)까지 이동하는 경로의 수를 출력한다. 이 값은 2^31-1보다 작거나 같다.
예제
| 입력 | 출력 |
|---|---|
4 5 50 45 37 32 30 35 50 40 20 25 30 30 25 17 28 27 24 22 15 10 | 3 |
풀이
DFS + 메모이제이션(Top-Down DP)으로 풀이한다.
dp[r][c]를 "(r, c)에서 목적지까지 도달하는 경로의 수"로 정의하되,Integer타입으로 선언하여 null로 미방문 표시dfs(r, c)재귀 함수:- 목적지(N-1, M-1)이면 1 반환
dp[r][c]가 null이 아니면 메모이제이션된 값 반환dp[r][c] = 0으로 초기화 후, 4방향 탐색- 범위 내이고 현재 높이보다 낮은 칸으로 이동하여 dfs 결과 누적
- 결과를
dp[r][c]에 저장하고 반환
핵심 아이디어: "내리막"이라는 조건으로 그래프에 사이클이 없어 DAG가 형성되므로, DFS + 메모이제이션으로 중복 경로 계산 없이 효율적으로 경로 수를 구할 수 있다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day164BOJ1520내리막DFSDP { // 1520
static int N, M;
static int[][] map;
static Integer[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
dp = new Integer[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(dfs(0, 0));
br.close();
}
static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
private static int dfs(int r, int c) {
if (r == N - 1 && c == M - 1) {
return 1;
}
if (dp[r][c] == null) {
dp[r][c] = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (index(nr, nc))
continue;
if (map[nr][nc] < map[r][c])
dp[r][c] += dfs(nr, nc);
}
}
return dp[r][c];
}
private static boolean index(int nr, int nc) {
return nr < 0 || nc < 0 || nr >= N || nc >= M;
}
}복잡도
- 시간: O(M × N)
- 공간: O(M × N)