[백준] 1520 내리막 길 - JAVA

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

1520번: 내리막 길

 

 

[알고리즘]

• DFS + DP 
• 출발지에서 도착지까지의 경로를 찾기위해 그래프 탐색 방법 중 DFS 구현 (최단거리 구하기 x) 
• 🌟고려해야 할 부분 
  1. 그래프의 최대 크기 : 500 x 500
  2. 모든 지점에서 4방향으로 이동이 가능할 경우, 스택에 엄청난 재귀함수가 쌓이면서 메모리초과가 발생 할 수 있다. 
  3. DP를 사용하여 이미 탐색한 경로에 대해서는 중복 연산을 제거한다. 
• dp[x][y] = 해당 지점에서 목표지점까지 갈 수 있는 경로의 수  

---

 

[설계]

• dp 값을 0이 아닌 -1 로 초기화한다. 
  1. 이미 탐색했던 경로에 대해서는 중복 탐색하지 않기 위해 dp 사용 
  2. 즉, 각 위치에 대해 (아직 탐색하지 않은 위치 = -1 ) / (이미 탐색했지만 경로가 없음) 을 구분해야 한다.
• dp 값에 따른 표시 
  1. dp[x][y] = -1 : 아직 탐색하지 않은 지점
  2. dp[x][y] = 0 : 탐색했지만, 목적지에 도달할 수 없는 지점 (가능한 경로 0개) 
  3. dp[x][y] = n(>0) : 탐색하였고, 목적지에 도달할 수 있는 경로가 n개 
• DFS 탐색의 재귀호출을 통해, 4방향 중 내리막길로 이동하면서 목적지에 도착했을 경우 1, 이미 탐색한 경로를 만났을 경우 해당 dp값을 반환하여 현재 경로에 더해준다.

---

 

[구현 과정]

• map[][] : 입력값으로 주어지는 지도 정보 저장 배열 
• dp[x][y] : (x,y) 위치에서 목적지인 (N-1, M-1) 까지의 가능한 경로의 수 

 

1. 입력값으로 주어지는 지도 값을 int형 2차원 배열인 map에 저장한다. 

 

2. dp배열을 map 과 같은 크기로 생성 후, -1로 초기화한다. (-1 == 아직 탐색하지 않은 지점) 

 

3. (0,0)인 시작점에서 부터 DFS 탐색을 시작한다. 

 

4. DFS 구현 과정은 다음과 같다.

• 현재 탐색하고 있는 지점(x,y) 의 dp 값을 0으로 바꾼다. (탐색한 지점이라는 표시)
• 4방향으로 탐색하며 지도의 범위를 벗어날 경우 continue 
• 이동할 수 있는 내리막길일 경우, 현재위치의 dp값에 다음 위치(nx,ny)의 dfs 결과값을 더한다. (재귀호출하다가 이후에 return 되는 값이 더해짐)
• 목적지에 도착했다면 1을 반환한다. 
• 만약 dp값이 -1이 아닌 지점을 만났다면 이미 탐색한 경로이므로 중복 탐색할 필요가 없다. 저장되어있는 dp값 반환.
  👉 저장되어있는 dp값 : 해당 위치로부터 목적지까지의 가능한 경로 수  
• 반환된 값은 재귀를 벗어나며 이동해 온 모든 지점의 dp값에 더해진다. 

 

 

5. 최종적으로 dp[0][0] 출력. (=시작점에서 목적지까지의 가능한 경로의 수) 

 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	static int N,M;
	static int[][] map; 
	static int[][] 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 int[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());
			}
		}
		
		for(int i=0; i<N; i++) {
			Arrays.fill(dp[i], -1);
		} 
        
		int res= dfs(0,0); 
		System.out.println(res);

	}//end of main
	
	static int dx[]= {-1,0,1,0};
	static int dy[]= {0,-1,0,1}; //상 좌 하 우 
	
	//0,0에서 시작하여 깊이우선 탐색 
	private static int dfs(int x, int y) {
		if(x==N-1 && y==M-1) return 1; //목적지까지의 경로 1추가
		
		if(dp[x][y] != -1) return dp[x][y]; //이미 한번 탐색한 경로 등장 
		
		dp[x][y] =0; //해당 위치에서 탐색 
		for(int d=0; d<4; d++) {
			int nx = x+dx[d];
			int ny = y+dy[d]; 
			
			if(isOut(nx, ny)) continue;
			
			//이동 가능 
			if(map[nx][ny] < map[x][y]) {
				dp[x][y] += dfs(nx,ny); 
			}
		}
        
		return dp[x][y];
	}
	
	private static boolean isOut(int x, int y) {
		return x<0 || x>=N || y<0 || y>=M; 
	}
}//end of class