처음에는.. 톡방에서 이야기 했다시피 완전탐색으로 풀었는데..잘 생각해보니 탐색을 해야하는 맵의 크기가 500*500 으로 25만이어서.. 그걸 N^2으로 풀게되면 굉장히 끔찍한 결과가 나오게 된다.
후....아무리 생각해도 DP로 풀 방법이 떠오르지 않아 함께 스터디 하는 두분의 코드를 적극 참조하였다..
감사합니다 두분.. 그리고 두분 코드를 참조하여서 다음부터는 4방향을 확인하는 코드는 dx,dy를 만들어서 for문으로 만들도록..
아무튼 기본적으로는 DFS로 깊이로 들어가야 한다. BFS로는 안되는 이유가 우선 백트래킹이 불가능하다. 동일한 경로를 다시 방문할 확률이 있기 때문에 완전탐색이 되게 되는데 그렇게 된다면 처음 얘기했던 끔찍한 시간 복잡도가 나타나게 된다.
근데 DFS로 동일한 경로의 깊이 들어가면 똑같이 시간 복잡도가..끔찍해진다.
그래서 기존 경로일 경우에는 DP에 사전에 저장해놓으면 방문할 필요가 없다는 특징을 이용한다.
DP로 풀는데에 가장 핵심은 같은 경로를 재 방문 하지 않는거고 DP에는 이 경로를 거친 횟수가 몇번인지를 표시하는 것이다. 초기화를 -1로 시켜놓고 만약에 처음으로 방문한다면(-1이라면) 0으로 초기화 한다. 그 후, MAP의 가장 끝 부분은 단 한번만 방문하기 때문에 사전에 1로 초기화 또는 return해주고 갔던 경로를 다시 돌아가면서 그 경로에 값을 반환하면서 더해간다. 그러다 보면 다른 경로로 가게 될 텐데 그 다른 경로가 만약에 이미 방문한 경로라면 결국 동일한 길을 따라가는 것이기 때문에 최근에 경로에 방문한 값을 return하면서 그 값을 경로를 되돌아가며 경로의 DP에 더해준다.(가다가 다른 경로로 빠지는건 동일한 길이니까..)
그것을 반복하다 탐색이 완료되면 DP[0][0]이 경로들의 합이다.
import java.io.*;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[][] map;
static int[][] DP;
static int answer=0;
static int N;
static int M;
static int dfs(int Y, int X){
if(Y==M-1&&X==N-1){
return 1;
}
if(Y>M||X>N||Y<0||X<0)
return -1;
if(DP[Y][X]==-1){
DP[Y][X]=0;
if((X+1<N)&&map[Y][X+1]<map[Y][X])
DP[Y][X]+=dfs(Y,X+1);
if((Y+1<M)&&map[Y+1][X]<map[Y][X])
DP[Y][X]+=dfs(Y+1,X);
if((Y-1>=0)&&map[Y-1][X]<map[Y][X])
DP[Y][X]+=dfs(Y-1,X);
if((X-1>=0)&&map[Y][X-1]<map[Y][X])
DP[Y][X]+=dfs(Y,X-1);
}
return DP[Y][X];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String a = br.readLine();
st = new StringTokenizer(a);
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());;
map= new int[M][N];
DP = new int[M][N];
for(int[] row: DP)
Arrays.fill(row,-1);
DP[M-1][N-1]=1;
for(int i=0;i<M;i++){
String temp = br.readLine();
st = new StringTokenizer(temp);
int j=0;
while (st.hasMoreTokens()){
map[i][j++]=Integer.parseInt(st.nextToken());
}
}
dfs(0,0);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(Integer.toString(DP[0][0]));
bw.flush();
bw.close();
}
}