[BOJ] 백준 1520번 내리막 길 (Java)

#1520 내리막 길

난이도 : 골드 4

유형 : DP / DFS

1520번: 내리막 길

▸ 문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

▸ 출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

 

문제 풀이  

본질적으로는 그래프 탐색 문제이다. (0,0)에서 출발하여 (n-1, m-1)로 가는 경우의 수를 모두 구해주면 된다. 이는 최단거리 탐색이 아니라 특정 지점으로의 경우의 수를 구하는 유형이므로 BFS보다는 DFS탐색이 더 유용할 듯 하다.

구상

그러므로 기본 베이스는 DFS탐색으로 잡고 시작하자.

• 그런데 여기서 그래프의 최대 크기는 500x500이다.

이는 재귀호출마다 매번 4방향 탐색을 2500번 하게되니 최악의 경우 엄청난 연산량(4^2500)을 요구한다. 그래서 그냥 DFS탐색만 할 경우 스택에 엄청난 재귀함수가 쌓이면서 메모리초과가 발생할 것이다. 그러므로 DP를 사용하여 중복되는 연산을 제거시켜줘야 한다.

• dp[x][y] = 내리막 길 경우의 수

 

설계

1. (0,0)을 시작점으로 DFS 탐색을 시작한다.
2. 4방향을 탐색하며 현재 그래프의 값(pos)보다 작은 그래프의 값(nxt)을 지닌 구역만 탐색한다. 
   1. (n-1, m-1)에 도착하면 1을 카운트해주고 해당 경로는 탐색을 종료한다.
   2. 방문 여부는 따로 체크해 줄 필요없이 dp값을 0으로 초기화시켜주면서 체크해주면 된다. dp[x][y]=0
      1. 그러기위해서는 dp값을 -1로 초기화 시켜줘야한다.
3. 재귀 탐색이 끝나면 최종적으로 dp[0][0]의 값을 출력해주면 된다. (dfs(0,0) == dp[0][0])

 

풀이 코드 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n,m;
	static int[][] map, dp;	
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		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++) {
			Arrays.fill(dp[i], -1);
		}
		
		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));
	}
	static int dfs(int x, int y) {
		if(x == n-1 && y == m-1) return 1;
		if (dp[x][y] != -1) return dp[x][y];
		
		int pos = map[x][y];
		dp[x][y] = 0;
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx <0 || nx > n-1 || ny < 0 || ny > m-1) continue;
			
			int nxt = map[nx][ny];
			if (pos > nxt) {
				dp[x][y] += dfs(nx, ny);
			}
		}
		return dp[x][y];
	}
}