[프로그래머스(Programmers)][자바(java)] (Lv3) 보행자 천국

 

programmers.co.kr/learn/courses/30/lessons/1832

코딩테스트 연습 - 보행자 천국

 

문제 풀이

 

▶  DFS  -->  시간 초과

public class Solution {
	
	int MOD = 20170805;
	int cnt;
	
	public void dp_cntWay( int x, int y, int m, int n, int c[][], char d ) {
		if( x < 0 || x >= m || y < 0 || y >= n )
			return;
		if( x == m-1 && y == n-1 ) {
			cnt = ( cnt + 1 ) % MOD;
			return;
		}
		if( c[x][y] == 1 )
			return;
		if( c[x][y] == 2 ) {
			if( d == 'D' )
				dp_cntWay( x+1, y, m, n, c, d );
			else if( d == 'R' )
				dp_cntWay( x, y+1, m, n, c, d );
			return;
		}
		dp_cntWay( x+1, y, m, n, c, 'D' );
		dp_cntWay( x, y+1, m, n, c, 'R' );
	}
	
	public int solution(int m, int n, int[][] cityMap) {
		cnt = 0;
		dp_cntWay( 0, 0, m, n, cityMap, ' ' );
		return cnt % MOD;
	}

}

 

▶  DFS + DP ( 2차원배열 )  -->  틀림

public class Solution {
	
	int MOD = 20170805;
	
	public int dp_cntWay( int x, int y, int m, int n, int dp[][], int c[][], char d ) {
		if( x < 0 || x >= m || y < 0 || y >= n )
			return 0;
		if( x == m-1 && y == n-1 )
			return 1;
		if( dp[x][y] > 0 )
			return dp[x][y] % MOD;
		if( c[x][y] == 1 )
			return 0;
		if( c[x][y] == 2 ) {
			if( d == 'D' )
				dp[x][y] += ( dp_cntWay( x+1, y, m, n, dp, c, d ) ) % MOD;
			else if( d == 'R' )
				dp[x][y] += ( dp_cntWay( x, y+1, m, n, dp, c, d ) ) % MOD;
			return dp[x][y] % MOD;
		}
		dp[x][y] += ( dp_cntWay( x+1, y, m, n, dp, c, 'D' ) ) % MOD;
		dp[x][y] += ( dp_cntWay( x, y+1, m, n, dp, c, 'R' ) ) % MOD;
		return dp[x][y] % MOD;
	}
	
    public static int solution(int m, int n, int[][] cityMap) {
    	int dp[][] = new int[m][n];
        return dp_cntWay( 0, 0, m, n, dp, cityMap, ' ' ) % MOD;
    }

}

 

▶  DFS + DP ( 3차원배열 )

# 1

public class Solution {
	
	int MOD = 20170805;
	
	public int dp_dfs_cntWay( int x, int y, int m, int n, int dp[][][], int c[][], int d ) {
		if( x < 0 || x >= m || y < 0 || y >= n )
			return 0;
		if( x == m-1 && y == n-1 )
			return 1;
		if( dp[x][y][d] > 0 )
			return dp[x][y][d] % MOD;
		if( c[x][y] == 1 )
			return 0;
		if( c[x][y] == 2 ) {
			if( d == 0 )
				dp[x][y][d] += ( dp_dfs_cntWay( x+1, y, m, n, dp, c, d ) ) % MOD;
			else if( d == 1 )
				dp[x][y][d] += ( dp_dfs_cntWay( x, y+1, m, n, dp, c, d ) ) % MOD;
			return dp[x][y][d] % MOD;
		}
		dp[x][y][d] += ( dp_dfs_cntWay( x+1, y, m, n, dp, c, 0 ) ) % MOD;
		dp[x][y][d] += ( dp_dfs_cntWay( x, y+1, m, n, dp, c, 1 ) ) % MOD;
		return dp[x][y][d] % MOD;
	}
	
	public int solution( int m, int n, int[][] cityMap ) {
		int dp[][] = new int[m][n][2];
		return dp_dfs_cntWay( 0, 0, m, n, dp, cityMap, 0 ) % MOD;
	}

}

# 2

public class Solution {
	
	int MOD = 20170805;
	int dx[] = { 1, 0 }, dy[] = { 0, 1 };
	
	public int dp_dfs_cntWay( int x, int y, int d, int m, int n, int dp[][][], int c[][] ) {
		if( x == m-1 && y == n-1 )
			return 1;
		if( dp[x][y][d] > 0 )
			return dp[x][y][d] % MOD;
		int nx, ny, i;
		for( i = 0; i < 2; i++ ) {
			nx = x + dx[i];
			ny = y + dy[i];
			if( nx < 0 || nx >= m || ny < 0 || ny >= n )
				continue;
			if( c[x][y] == 0 || ( c[x][y] == 2 && d == i ) )
				dp[x][y][d] += ( dp_dfs_cntWay( nx, ny, i, m, n, dp, c ) ) % MOD;
		}
		return dp[x][y][d] % MOD;
	}
    	
	public int solution( int m, int n, int[][] cityMap ) {
		int dp[][] = new int[m][n][2];
		return dp_dfs_cntWay( 0, 0, 0, m, n, dp, cityMap ) % MOD;
	}
    
}

 

*  DP

-  dp[x][y][d]  =>  ( x, y )에서 ( m-1, n-1 )까지 갈 수 있는 경우의 수  ( d가 0이면 아래쪽, 1이면 오른쪽 )