처음엔 단순 DFS만으로 풀릴 것이라 생각하여 4방 탐색과 visit을 이용해 구현하였는데, 약 13% 부근에서 시간초과가 발생했다.
백트래킹을 딱히 해주지 않았기에 가지치기 문제인가 고민했지만, 현재 위치보다 낮은 다음위치를 찾는 조건 이외의 가지치기를 할 조건이 떠오르지 않았다.
결과적으로 이 문제는 DP를 사용해 해결할 수 있었다.
처음에 DP로 풀 수 있는가 고민했을 때, 위에서 아래로 순차적으로 값이 쌓이는게 아닌, 다른 경로를 통해 위쪽으로 다시 돌아올 수 있어 불가능하다 생각했다. 다만 이는 Buttom-up 방식일 때 불가능한 경우이고, Top-down 방식으로 도착지로부터 다시 돌아오며 진행했던 경로의 도달가능성을 쌓아나갈 수 있었다.
package day0410;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
* Top-down 방식의 DP 풀이
*
*/
public class acmicpc1520_내리막길 {
static int M, N, answer;
static int[][] map, dp;
static int[] dr = {0, 1, 0, -1};
static int[] dc = {1, 0, -1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[M][N];
dp = new int[M][N];
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
dp[i][j] = -1;
}
} // end input
System.out.println(DFS(0, 0));
}
static int DFS(int r, int c) {
if (r == M-1 && c == N-1) {
return 1;
}
/*
* dp 초기값이 0이 아닌 -1인 이유
*
* 만약 목표지점까지 도달하지 못한다면 0이 반환될텐데 이를 차후 DFS가 다시 방문했을때
* 아직 방문하지 않은 점인지, 가봤는데 경로가 없는 점인지 구분을 할 수 없어
* 다시 DFS를 재 수행하게 된다.
*
*/
if (dp[r][c] != -1) return dp[r][c];
dp[r][c] = 0;
for(int dir=0; dir<4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
if (isValid(nr, nc) && map[r][c] > map[nr][nc]) {
dp[r][c] += DFS(nr, nc);
}
}
return dp[r][c];
}
static boolean isValid(int r, int c) {
return 0 <= r && r < M && 0 <= c && c < N;
}
static void print() {
for(int i=0; i<M; i++) {
for(int j=0; j<N; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
}
알고리즘 문제를 풀면서 Top-down 방식의 DP를 구현해본건 처음이었다. 기존에는 for문을 사용한 Buttom-up 방식만 사용했어서, DP로는 풀이가 불가능하다 생각했는데 아니었다. Top-down 방식의 값 누적 방식을 좀 더 정리해봐야겠다.