[백준(Baekjoon)][자바(java)] 1520 : 내리막 길 / 동적 계획법 2

 

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

문제 풀이

 

▶  DFS   --> 시간 초과

import java.util.Scanner;

public class Main {
	
	static int m, n, map[][], dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
	static int cnt = 0;
	
	public static void dfs_cntWay( int x, int y ) {
		if( x == m-1 && y == n-1 )
			cnt++;
		for( int u = 0; u < 4; u++ ) {
			int nx = x + dx[u], ny = y + dy[u];
			if( nx >= 0 && nx < m && ny >= 0 && ny < n && map[x][y] > map[nx][ny] )
				dfs_cntWay( nx, ny );
		}		
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt(); n = sc.nextInt();
		map = new int[m][n]; 
		int i, j;
		for( i = 0; i < m; i++ )
			for( j = 0; j < n; j++ )
				map[i][j] = sc.nextInt();
		sc.close();
		
		dfs_cntWay( 0, 0 );

		System.out.println( cnt );
        
	}
}

 

▶  DFS + DP

import java.util.Scanner;

public class Main {
	
	static int m, n, map[][], dp[][], dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
	
	public static int dfs_dp_cntWay( int x, int y ) {
		if( x == m-1 && y ==  n-1 )
			return 1;
		if( dp[x][y] == -1 ) {
			dp[x][y] = 0;
			for( int u = 0; u < 4; u++ ) {
				int nx = x + dx[u], ny = y + dy[u];
				if( nx >= 0 && nx < m && ny >= 0 && ny < n && map[x][y] > map[nx][ny] )
					dp[x][y] += dfs_dp_cntWay( nx, ny );
			}
		}
		return dp[x][y];
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt(); 
		n = sc.nextInt();
		map = new int[m][n]; 
		int i, j;
		for( i = 0; i < m; i++ )
			for( j = 0; j < n; j++ )
				map[i][j] = sc.nextInt();
		sc.close();
		
		dp = new int[m][n];
		for( i = 0; i < m; i++ )
			for( j = 0; j < n; j++ )
				dp[i][j] = -1;

		System.out.println( dfs_dp_cntWay( 0, 0 ) );
        
	}
}