보행자 천국

Dynamic Programming 문제이다.

카카오 코드 페스티벌 문제이다. DP가 약해서 그런것도 있었지만, 하나의 2차원 배열에 풀려고 했던것이 시작부터 난관에 빠진느낌이었다. 하나의 2차원배열에 풀려다 보니, 중복된 경로가 체크되어 정확한 답이 도출이 되지않았다.

그래서 풀이를 보니, 2개의 2차원 배열이 필요했다.

그다음 입력된 cityMap이 0,1,2에 따라 값이 달랐는데

0의 경우는 어디든지 이동이 가능하므로, 이전방향에서 오는 2개의 2차원 배열의 경우의 수를 더해주면 된다.

1의 경우는 이동이 불가능하므로, 0을 채워야 한다

2의 경우는 이전방향을 유지하면서 계속 가줘야 하기때문에, 이전방향의 2차원 배열을 그대로 옮긴다.

마지막으로 예외처리를 하지 않기 위해서 (0,0)이 아닌 (1,1)에서 시작을 했기 때문에, 목표지점은 (m,n)이 된다.

그래서 해당하는 답은 (m,n)으로 가는 경우의 수이다.

그 경우의 수는 (m-1,n)에서 아래로 가는 경우 + (m,n-1)에서 오른쪽으로 가는 경우이다

이것을 그대로 옮기면 down[m-1][n] + right[m][n-1]이 된다.

단 중간에 값이 커질수 있기 때문에, MOD연산을 계속 해줘야한다!!

by Java

class Solution {
  int MOD = 20170805;
  int gox[] = {0,1,-1,0};
  int goy[] = {1,0,0,-1};
  public int solution(int m, int n, int[][] cityMap) {
      int[][] down = new int[m+1][n+1];
      int[][] right = new int[m+1][n+1];
      down[1][1] = 1;
      right[1][1] = 1;
      for(int i=1;i<=m;i++) {
          for(int j=1;j<=n;j++) {
              if(cityMap[i-1][j-1]==0) {
                  down[i][j]+=(down[i-1][j]+right[i][j-1])%MOD;
                  right[i][j]+=(down[i-1][j]+right[i][j-1])%MOD;
              }
              else if(cityMap[i-1][j-1]==1) {
                  down[i][j]=0;
                  right[i][j]=0;
              }
              else {
                  down[i][j]+=down[i-1][j]%MOD;
                  right[i][j]+=right[i][j-1]%MOD;
              }
          }
      }
      return (down[m-1][n]%MOD+right[m][n-1]%MOD)%MOD; // 위에서 아래로 내려오는 경우의수 + 왼쪽에서 오른쪽으로 가는 경우의수
  }
}