[프로그래머스] 보행자 천국 (Java)

프로그래머스 보행자 천국

문제풀이

이전의 이동방향을 기억해야한다는 점에서 BOJ 17070 파이프 옮기기1 문제가 떠올랐다. 이 문제에서는 아래쪽 또는 오른쪽으로 이동할 수 있으므로 두 방향을 저장할 수 있도록 하였다.

보통 이런 문제를 풀 때 dp[i][j]가 나타내는 바는 [i][j]에 도달할 수 있는 경우의 수를 나타내는 경우가 많았는데, 여기서는 [i][j]에서 오른쪽과 아래쪽으로 이동할 수 있는 경우의 수다.

• dp배열에 패딩을 넣어준다. 첫 반복에서 [i - 1] 과 [j - 1]이 배열 범위를 넘지 않게하기 위함
• 시작점 dp[i][j]를 1로 초기화한다.
• cityMap[i][j]의 숫자에 따라서 dp배열을 갱신한다.
• 도착점은 무조건 0이기 때문에 dp[m][n][0]과 dp[m][n][1]은 같다.

구현코드

class Solution {
	  int MOD = 20170805;
	  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 r = 1 ; r <= m ; ++r){
              for(int c = 1 ; c <= n ; ++c){
                  if(cityMap[r - 1][c - 1] == 0){
                      dp[r][c][0] += (dp[r - 1][c][0] + dp[r][c - 1][1]) % MOD;
                      dp[r][c][1] += (dp[r - 1][c][0] + dp[r][c - 1][1]) % MOD;
                  } else if(cityMap[r - 1][c - 1] == 1){
                      dp[r][c][0] = 0;
                      dp[r][c][1] = 0;
                  } else {
                      dp[r][c][0] = dp[r - 1][c][0];
                      dp[r][c][1] = dp[r][c - 1][1];
                  }
              }
          }
          return dp[m][n][0]; 
      }
}