<Algorithm> 206. 보행자천국(Programmers)

1. 보행자천국(Programmers)

   사용 알고리즘 :  DP

• 예전에 많이 풀어봤던 경우의 수 누적 문제인 것 같아서 같은 방식으로 접근했지만 시간초과가 발생한 문제 

• 단순히 2차원 배열 두개로 흐름을 나눠서 누적 방식도 이중포문만으로 구성해서 O(N^2)로 할 수 있는 것을 보고 놀라웠다.

문제에 대한 접근&생각

1. m, n의 최대 크기 500 -> 한번 방문했던 곳은 재방문 없이 경우의 수만 처리 -> DP!
2. DFS 형태로 구현 -> 시간초과! -> 2차원 배열 누적형태 ! 

코드 

public class Solution {
    
    public static void main(String[] args) {
        System.out.println(new Solution()
                .solution(3, 6, new int[][]{{0, 2, 0, 0, 0, 2}, {0, 0, 2, 0, 1, 0}, {1, 0, 0, 2, 2, 0}}));
    }
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int[][] V = new int[m+1][n+1];
        int[][] H = new int[m+1][n+1];
        V[1][1] = 1; //왼쪽에서 오는경우
        H[1][1] = 1; //아래에서 오는경우
        /***************************
         * DP를 이용하여 갈수있는 경우의 수를
         * 누적한다. 이때 두개의 배열을 두어서
         * 각 방향에 대한 값을 따로 누적 시켜서
         * 모든 경우의 수를 구한다.
         ***************************/
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(cityMap[i-1][j-1] == 0) {
                    // (i-1),(j-1)에 해당하는 값이 i j에 영향을 준다. 
                    V[i][j] += V[i-1][j]%MOD+H[i][j-1]%MOD;
                    H[i][j] += V[i-1][j]%MOD+H[i][j-1]%MOD;
                    // 모든 방향으로 진입할 수 있기 때문에 값은 누적된다.
                }else if(cityMap[i-1][j-1]==2) {
                    V[i][j] = V[i-1][j];
                    H[i][j] = H[i][j-1];
                    // 한가지 방향으로만 진입하기 때문에 이전방향과 같아진다. 
                }
            }
        }
        return V[m][n]%MOD;
        // 모든 경우의 수가 저장된다.
    }
}
 
public class Solution {
    
    public static void main(String[] args) {
        System.out.println(new Solution()
                .solution(3, 6, new int[][]{{0, 2, 0, 0, 0, 2}, {0, 0, 2, 0, 1, 0}, {1, 0, 0, 2, 2, 0}}));
    }
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
          dp = new int[m][n][2];
          solve(0, 0, m, n, cityMap, 0);
      return dp[0][0][0]+dp[0][0][1];
   }
   static int dx[] = {0,1}; // 하,우
   static int dy[] = {1,0};
   static int dp[][][];
   
   public int solve(int x,int y,int m, int n,int[][] cityMap, int dir) {
       
       if(x > m-1 || y > n-1 ) 
           return 0;       
       if(x == m-1 && y == n-1 ) 
           return 1;
       
       if(dp[x][y][dir] != 0) 
           return dp[x][y][dir];
 
       if(cityMap[x][y] == 0) {
           dp[x][y][0] += solve(x+1, y, m, n, cityMap, 0)%MOD;
           dp[x][y][1] += solve(x, y+1, m, n, cityMap, 1)%MOD;
       }else if(cityMap[x][y] == 2) {
           if(dir == 0) {
               dp[x][y][0] += solve(x+1, y, m, n, cityMap, 0)%MOD;
           }else {
               dp[x][y][1] += solve(x, y+1, m, n, cityMap, 1)%MOD;
           }
       }
       return dp[x][y][dir];
   }
   public boolean isBoundary(int m, int n, int nx, int ny) {
       if(nx < 0 || ny < 0 || nx >= m || ny >= n) return false;
       else return true;
   }
}
 

참고 & 출처  

https://www.acmicpc.net/board/view/20071

http://tech.kakao.com/2017/08/11/code-festival-round-1/