프로그래머스 - 보행자 천국

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 보행자 천국

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

풀이 1. (초급) - Right와 Down의 2차배열을 생성하여 DP 계산

class Solution {
  public int solution(int m, int n, int[][] cityMap) {
        int [][] right = new int [m+1][n+1];
	int [][] down = new int [m+1] [n+1];
	right[1][1] = down[1][1] = 1;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			switch(cityMap[i-1][j-1]) {
				case 0 : 
					right[i][j] += (right[i][j-1] + down[i-1][j]) % 20170805;
					down[i][j] += (down[i-1][j] + right[i][j-1]) % 20170805;
					break;
				case 2 :
					right[i][j] = right[i][j-1];
					down[i][j] = down[i-1][j];
					break;
			}
		}
	}
        return (right[m][n-1] + down[m-1][n]) % 20170805;
    }
}

풀이 2. (초급) - 3차배열로 Right와 Down을 분류하여 DP 계산
// 풀이 1과 방식은 비슷하나 3차 배열이라 속도가 다소 느린 것 같다.

class Solution {
	public int solution(int m, int n, int[][] cityMap) {
	 	// dp[][][0] 아래쪽, dp[][][1] 오른쪽
       	int [][][] dp = new int [m+1][n+1][2];
	dp[1][1][0] = dp[1][1][1] = 1;
		
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			switch(cityMap[i-1][j-1]) {
			case 0 : 
				dp[i][j][0] += (dp[i-1][j][0] + dp[i][j-1][1]) % 20170805;
				dp[i][j][1] += (dp[i-1][j][0] + dp[i][j-1][1]) % 20170805;
				break;
			case 2 :
				dp[i][j][0] = dp[i-1][j][0];
				dp[i][j][1] = dp[i][j-1][1];
				break;
			}
		}
	}
          return dp[m][n][1]; 
      }
}